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);
278 if(next_count->get_id() != rep->id)
280 // we're moving to a different repeat from the last
281 // one, so set up a counter object and recurse:
282 repeater_count<BidiIterator> r(rep->id, &next_count, position);
286 // If we've had at least one repeat already, and the last one
287 // matched the NULL string then set the repeat count to
290 next_count->check_null_repeat(position, rep->max);
292 // find out which of these two alternatives we need to take:
293 bool take_first, take_second;
296 take_first = rep->can_be_null & mask_take;
297 take_second = rep->can_be_null & mask_skip;
301 take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
302 take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
305 if(next_count->get_count() < rep->min)
307 // we must take the repeat:
310 // increase the counter:
312 pstate = rep->next.p;
313 return match_all_states();
317 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
320 // try and take the repeat if we can:
321 if((next_count->get_count() < rep->max) && take_first)
323 // store position in case we fail:
324 BidiIterator pos = position;
325 // increase the counter:
327 pstate = rep->next.p;
328 if(match_all_states())
330 // failed repeat, reset posistion and fall through for alternative:
338 return false; // can't take anything, fail...
342 // try and skip the repeat if we can:
345 // store position in case we fail:
346 BidiIterator pos = position;
348 if(match_all_states())
350 // failed alternative, reset posistion and fall through for repeat:
353 if((next_count->get_count() < rep->max) && take_first)
355 // increase the counter:
357 pstate = rep->next.p;
358 return match_all_states();
367 template <class BidiIterator, class Allocator, class traits>
368 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
371 #pragma warning(push)
372 #pragma warning(disable:4127)
375 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
376 re_syntax_base* psingle = rep->next.p;
377 // match compulsary repeats first:
378 while(count < rep->min)
385 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
389 while(count < rep->max)
396 if((rep->leading) && (count < rep->max))
399 return backtrack_till_match(count - rep->min);
403 // non-greedy, keep trying till we get a match:
404 BidiIterator save_pos;
407 if((rep->leading) && (rep->max == UINT_MAX))
412 if(match_all_states())
414 if(count >= rep->max)
428 template <class BidiIterator, class Allocator, class traits>
429 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
432 #pragma warning(push)
433 #pragma warning(disable:4127)
435 if(m_match_flags & match_not_dot_null)
436 return match_dot_repeat_slow();
437 if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
438 return match_dot_repeat_slow();
440 // start by working out how much we can skip:
442 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
444 #pragma warning(push)
445 #pragma warning(disable:4267)
447 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
448 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));
452 return false; // not enough text left to match
454 std::advance(position, count);
458 if((rep->leading) && (count < rep->max) && greedy)
461 return backtrack_till_match(count - rep->min);
463 // non-greedy, keep trying till we get a match:
464 BidiIterator save_pos;
467 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
472 if((rep->leading) && (rep->max == UINT_MAX))
477 if(match_all_states())
479 if(count >= rep->max)
483 position = ++save_pos;
491 template <class BidiIterator, class Allocator, class traits>
492 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
495 #pragma warning(push)
496 #pragma warning(disable:4127)
499 #pragma option push -w-8008 -w-8066 -w-8004
501 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
502 BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
503 const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
506 // start by working out how much we can skip:
508 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
509 std::size_t desired = greedy ? rep->max : rep->min;
510 if(::boost::is_random_access_iterator<BidiIterator>::value)
512 BidiIterator end = position;
513 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
514 BidiIterator origin(position);
515 while((position != end) && (traits_inst.translate(*position, icase) == what))
519 count = (unsigned)::boost::re_detail::distance(origin, position);
523 while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
529 if((rep->leading) && (count < rep->max) && greedy)
535 return backtrack_till_match(count - rep->min);
537 // non-greedy, keep trying till we get a match:
538 BidiIterator save_pos;
541 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
543 if((traits_inst.translate(*position, icase) == what))
549 return false; // counldn't repeat even though it was the only option
551 if((rep->leading) && (rep->max == UINT_MAX))
556 if(match_all_states())
558 if(count >= rep->max)
563 if(traits_inst.translate(*position, icase) == what)
581 template <class BidiIterator, class Allocator, class traits>
582 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
585 #pragma warning(push)
586 #pragma warning(disable:4127)
589 #pragma option push -w-8008 -w-8066 -w-8004
591 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
592 const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
595 // start by working out how much we can skip:
597 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
598 std::size_t desired = greedy ? rep->max : rep->min;
599 if(::boost::is_random_access_iterator<BidiIterator>::value)
601 BidiIterator end = position;
602 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
603 BidiIterator origin(position);
604 while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
608 count = (unsigned)::boost::re_detail::distance(origin, position);
612 while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
618 if((rep->leading) && (count < rep->max) && greedy)
624 return backtrack_till_match(count - rep->min);
626 // non-greedy, keep trying till we get a match:
627 BidiIterator save_pos;
630 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
632 if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
638 return false; // counldn't repeat even though it was the only option
640 if((rep->leading) && (rep->max == UINT_MAX))
645 if(match_all_states())
647 if(count >= rep->max)
652 if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
670 template <class BidiIterator, class Allocator, class traits>
671 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
674 #pragma warning(push)
675 #pragma warning(disable:4127)
678 #pragma option push -w-8008 -w-8066 -w-8004
680 typedef typename traits::char_class_type char_class_type;
681 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
682 const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
685 // start by working out how much we can skip:
687 bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
688 std::size_t desired = greedy ? rep->max : rep->min;
689 if(::boost::is_random_access_iterator<BidiIterator>::value)
691 BidiIterator end = position;
692 std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
693 BidiIterator origin(position);
694 while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
698 count = (unsigned)::boost::re_detail::distance(origin, position);
702 while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
708 if((rep->leading) && (count < rep->max) && greedy)
714 return backtrack_till_match(count - rep->min);
716 // non-greedy, keep trying till we get a match:
717 BidiIterator save_pos;
720 while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
722 if(position != re_is_set_member(position, last, set, re.get_data(), icase))
728 return false; // counldn't repeat even though it was the only option
730 if((rep->leading) && (rep->max == UINT_MAX))
735 if(match_all_states())
737 if(count >= rep->max)
742 if(position != re_is_set_member(position, last, set, re.get_data(), icase))
760 template <class BidiIterator, class Allocator, class traits>
761 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
764 #pragma warning(push)
765 #pragma warning(disable:4127)
767 if((m_match_flags & match_partial) && (position == last))
768 m_has_partial_match = true;
770 const re_repeat* rep = static_cast<const re_repeat*>(pstate);
771 BidiIterator backtrack = position;
774 if(rep->can_be_null & mask_skip)
777 if(match_all_states())
782 position = --backtrack;
790 while(count && !can_start(*position, rep->_map, mask_skip))
797 backtrack = position;
798 if(match_all_states())
802 position = --backtrack;
811 } // namespace re_detail
814 #ifdef BOOST_HAS_ABI_HEADERS
815 # include BOOST_ABI_SUFFIX