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 recursive implementation.
20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
21 #define BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
23 #ifdef BOOST_HAS_ABI_HEADERS
24 # include BOOST_ABI_PREFIX
30 template <class BidiIterator>
34 sub_match<BidiIterator> sub;
37 backup_subex(const match_results<BidiIterator, A>& w, int i)
38 : index(i), sub(w[i], false) {}
40 void restore(match_results<BidiIterator, A>& w)
42 w.set_first(sub.first, index);
43 w.set_second(sub.second, index, sub.matched);
45 const sub_match<BidiIterator>& get() { return sub; }
48 template <class BidiIterator, class Allocator, class traits>
49 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
51 static matcher_proc_type const s_match_vtable[29] =
53 (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
54 &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
55 &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
56 &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
57 &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
58 &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
59 &perl_matcher<BidiIterator, Allocator, traits>::match_match,
60 &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
61 &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
62 &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
63 &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
64 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
65 &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
66 &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
67 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
68 &perl_matcher<BidiIterator, Allocator, traits>::match_set,
69 &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
70 &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
71 &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
72 &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
73 &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
74 &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
75 (::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),
76 &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
77 &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
78 &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
79 &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
80 &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
81 &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
84 if(state_count > max_state_count)
85 raise_error(traits_inst, regex_constants::error_space);
88 matcher_proc_type proc = s_match_vtable[pstate->type];
92 if((m_match_flags & match_partial) && (position == last) && (position != search_base))
93 m_has_partial_match = true;
100 template <class BidiIterator, class Allocator, class traits>
101 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
103 int index = static_cast<const re_brace*>(pstate)->index;
108 pstate = pstate->next.p;
113 // forward lookahead assert:
114 BidiIterator old_position(position);
115 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
116 pstate = pstate->next.p->next.p;
117 r = match_all_states();
118 pstate = next_pstate;
119 position = old_position;
120 if((r && (index != -1)) || (!r && (index != -2)))
128 // independent sub-expression:
129 bool old_independent = m_independent;
130 m_independent = true;
131 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
132 pstate = pstate->next.p->next.p;
133 r = match_all_states();
134 pstate = next_pstate;
135 m_independent = old_independent;
136 #ifdef BOOST_REGEX_MATCH_EXTRA
137 if(r && (m_match_flags & match_extra))
140 // our captures have been stored in *m_presult
141 // we need to unpack them, and insert them
142 // back in the right order when we unwind the stack:
145 match_results<BidiIterator, Allocator> tm(*m_presult);
146 for(i = 0; i < tm.size(); ++i)
147 (*m_presult)[i].get_captures().clear();
148 // match everything else:
149 r = match_all_states();
150 // now place the stored captures back:
151 for(i = 0; i < tm.size(); ++i)
153 typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
154 seq& s1 = (*m_presult)[i].get_captures();
155 const seq& s2 = tm[i].captures();
167 // conditional expression:
168 const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
169 BOOST_ASSERT(alt->type == syntax_element_alt);
170 pstate = alt->next.p;
171 if(pstate->type == syntax_element_assert_backref)
173 if(!match_assert_backref())
179 // zero width assertion, have to match this recursively:
180 BOOST_ASSERT(pstate->type == syntax_element_startmark);
181 bool negated = static_cast<const re_brace*>(pstate)->index == -2;
182 BidiIterator saved_position = position;
183 const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
184 pstate = pstate->next.p->next.p;
185 bool r = match_all_states();
186 position = saved_position;
190 pstate = next_pstate;
198 BOOST_ASSERT(index > 0);
199 if((m_match_flags & match_nosubs) == 0)
201 backup_subex<BidiIterator> sub(*m_presult, index);
202 m_presult->set_first(position, index);
203 pstate = pstate->next.p;
204 r = match_all_states();
206 sub.restore(*m_presult);
207 #ifdef BOOST_REGEX_MATCH_EXTRA
209 // we have a match, push the capture information onto the stack:
211 else if(sub.get().matched && (match_extra & m_match_flags))
212 ((*m_presult)[index]).get_captures().push_back(sub.get());
217 pstate = pstate->next.p;
225 template <class BidiIterator, class Allocator, class traits>
226 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
228 bool take_first, take_second;
229 const re_alt* jmp = static_cast<const re_alt*>(pstate);
231 // find out which of these two alternatives we need to take:
234 take_first = jmp->can_be_null & mask_take;
235 take_second = jmp->can_be_null & mask_skip;
239 take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
240 take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
245 // we can take the first alternative,
246 // see if we need to push next alternative:
249 BidiIterator oldposition(position);
250 const re_syntax_base* old_pstate = jmp->alt.p;
251 pstate = pstate->next.p;
252 if(!match_all_states())
255 position = oldposition;
259 pstate = pstate->next.p;
267 return false; // neither option is possible
270 template <class BidiIterator, class Allocator, class traits>
271 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
274 #pragma warning(push)
275 #pragma warning(disable:4127 4244)
277 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
279 // Always copy the repeat count, so that the state is restored
280 // when we exit this scope:
282 repeater_count<BidiIterator> r(rep->id, &next_count, position);
284 // If we've had at least one repeat already, and the last one
285 // matched the NULL string then set the repeat count to
288 next_count->check_null_repeat(position, rep->max);
290 // find out which of these two alternatives we need to take:
291 bool take_first, take_second;
294 take_first = rep->can_be_null & mask_take;
295 take_second = rep->can_be_null & mask_skip;
299 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
300 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
303 if(next_count->get_count() < rep->min)
305 // we must take the repeat:
308 // increase the counter:
310 pstate = rep->next.p;
311 return match_all_states();
315 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
318 // try and take the repeat if we can:
319 if((next_count->get_count() < rep->max) && take_first)
321 // store position in case we fail:
322 BidiIterator pos = position;
323 // increase the counter:
325 pstate = rep->next.p;
326 if(match_all_states())
328 // failed repeat, reset posistion and fall through for alternative:
336 return false; // can't take anything, fail...
340 // try and skip the repeat if we can:
343 // store position in case we fail:
344 BidiIterator pos = position;
346 if(match_all_states())
348 // failed alternative, reset posistion and fall through for repeat:
351 if((next_count->get_count() < rep->max) && take_first)
353 // increase the counter:
355 pstate = rep->next.p;
356 return match_all_states();
365 template <class BidiIterator, class Allocator, class traits>
366 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
369 #pragma warning(push)
370 #pragma warning(disable:4127)
373 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
374 re_syntax_base* psingle = rep->next.p;
375 // match compulsary repeats first:
376 while(count < rep->min)
383 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
387 while(count < rep->max)
394 if((rep->leading) && (count < rep->max))
397 return backtrack_till_match(count - rep->min);
401 // non-greedy, keep trying till we get a match:
402 BidiIterator save_pos;
405 if((rep->leading) && (rep->max == UINT_MAX))
410 if(match_all_states())
412 if(count >= rep->max)
426 template <class BidiIterator, class Allocator, class traits>
427 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
430 #pragma warning(push)
431 #pragma warning(disable:4127)
433 if(m_match_flags & match_not_dot_null)
434 return match_dot_repeat_slow();
435 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
436 return match_dot_repeat_slow();
438 // start by working out how much we can skip:
440 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
442 #pragma warning(push)
443 #pragma warning(disable:4267)
445 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
446 std::size_t count = (std::min)(static_cast<std::size_t>(::boost::re_detail::distance(position, last)), static_cast<std::size_t>(greedy ? rep->max : rep->min));
450 return false; // not enough text left to match
452 std::advance(position, count);
456 if((rep->leading) && (count < rep->max) && greedy)
459 return backtrack_till_match(count - rep->min);
461 // non-greedy, keep trying till we get a match:
462 BidiIterator save_pos;
465 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
470 if((rep->leading) && (rep->max == UINT_MAX))
475 if(match_all_states())
477 if(count >= rep->max)
481 position = ++save_pos;
489 template <class BidiIterator, class Allocator, class traits>
490 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
493 #pragma warning(push)
494 #pragma warning(disable:4127)
495 #pragma warning(disable:4267)
498 #pragma option push -w-8008 -w-8066 -w-8004
500 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
501 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
502 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
504 // start by working out how much we can skip:
506 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
507 std::size_t count, desired;
508 if(::boost::is_random_access_iterator<BidiIterator>::value)
512 (std::size_t)(greedy ? rep->max : rep->min),
513 (std::size_t)::boost::re_detail::distance(position, last));
518 while(--desired && (traits_inst.translate_nocase(*position) == what))
525 while(--desired && (traits_inst.translate(*position) == what))
530 count = count - desired;
535 desired = greedy ? rep->max : rep->min;
536 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
542 if((rep->leading) && (count < rep->max) && greedy)
548 return backtrack_till_match(count - rep->min);
550 // non-greedy, keep trying till we get a match:
551 BidiIterator save_pos;
554 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
556 if((traits_inst.translate(*position, icase) == what))
562 return false; // counldn't repeat even though it was the only option
564 if((rep->leading) && (rep->max == UINT_MAX))
569 if(match_all_states())
571 if(count >= rep->max)
576 if(traits_inst.translate(*position, icase) == what)
594 template <class BidiIterator, class Allocator, class traits>
595 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
598 #pragma warning(push)
599 #pragma warning(disable:4127)
602 #pragma option push -w-8008 -w-8066 -w-8004
604 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
605 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
608 // start by working out how much we can skip:
610 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
611 std::size_t desired = greedy ? rep->max : rep->min;
612 if(::boost::is_random_access_iterator<BidiIterator>::value)
614 BidiIterator end = position;
615 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
616 BidiIterator origin(position);
617 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
621 count = (unsigned)::boost::re_detail::distance(origin, position);
625 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
631 if((rep->leading) && (count < rep->max) && greedy)
637 return backtrack_till_match(count - rep->min);
639 // non-greedy, keep trying till we get a match:
640 BidiIterator save_pos;
643 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
645 if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
651 return false; // counldn't repeat even though it was the only option
653 if((rep->leading) && (rep->max == UINT_MAX))
658 if(match_all_states())
660 if(count >= rep->max)
665 if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
683 template <class BidiIterator, class Allocator, class traits>
684 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
687 #pragma warning(push)
688 #pragma warning(disable:4127)
691 #pragma option push -w-8008 -w-8066 -w-8004
693 typedef typename traits::char_class_type char_class_type;
694 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
695 const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
698 // start by working out how much we can skip:
700 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
701 std::size_t desired = greedy ? rep->max : rep->min;
702 if(::boost::is_random_access_iterator<BidiIterator>::value)
704 BidiIterator end = position;
705 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
706 BidiIterator origin(position);
707 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
711 count = (unsigned)::boost::re_detail::distance(origin, position);
715 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
721 if((rep->leading) && (count < rep->max) && greedy)
727 return backtrack_till_match(count - rep->min);
729 // non-greedy, keep trying till we get a match:
730 BidiIterator save_pos;
733 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
735 if(position != re_is_set_member(position, last, set, re.get_data(), icase))
741 return false; // counldn't repeat even though it was the only option
743 if((rep->leading) && (rep->max == UINT_MAX))
748 if(match_all_states())
750 if(count >= rep->max)
755 if(position != re_is_set_member(position, last, set, re.get_data(), icase))
773 template <class BidiIterator, class Allocator, class traits>
774 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
777 #pragma warning(push)
778 #pragma warning(disable:4127)
780 if((m_match_flags & match_partial) && (position == last))
781 m_has_partial_match = true;
783 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
784 BidiIterator backtrack = position;
787 if(rep->can_be_null & mask_skip)
790 if(match_all_states())
795 position = --backtrack;
803 while(count && !can_start(*position, rep->_map, mask_skip))
810 backtrack = position;
811 if(match_all_states())
815 position = --backtrack;
824 } // namespace re_detail
827 #ifdef BOOST_HAS_ABI_HEADERS
828 # include BOOST_ABI_SUFFIX