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 * common to both the recursive and non-recursive versions.
20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
21 #define BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
23 #ifdef BOOST_HAS_ABI_HEADERS
24 # include BOOST_ABI_PREFIX
28 # pragma option push -w-8008 -w-8066
34 template <class BidiIterator, class Allocator, class traits>
35 void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)
37 typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;
38 typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;
42 // precondition failure: e is not a valid regex.
43 std::invalid_argument ex("Invalid regular expression object");
44 boost::throw_exception(ex);
48 estimate_max_state_count(static_cast<category*>(0));
49 expression_flag_type re_f = re.flags();
50 icase = re_f & regex_constants::icase;
51 if(!(m_match_flags & (match_perl|match_posix)))
53 if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
54 m_match_flags |= match_perl;
55 else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
56 m_match_flags |= match_perl;
58 m_match_flags |= match_posix;
60 if(m_match_flags & match_posix)
62 m_temp_match.reset(new match_results<BidiIterator, Allocator>());
63 m_presult = m_temp_match.get();
66 m_presult = &m_result;
67 #ifdef BOOST_REGEX_NON_RECURSIVE
71 // find the value to use for matching word boundaries:
72 m_word_mask = re.get_data().m_word_mask;
73 // find bitmask to use for matching '.':
74 match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? re_detail::test_not_newline : re_detail::test_newline);
77 template <class BidiIterator, class Allocator, class traits>
78 void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)
80 static const difference_type k = 100000;
81 difference_type dist = boost::re_detail::distance(base, last);
82 traits_size_type states = static_cast<traits_size_type>(re.size());
84 difference_type lim = ((std::numeric_limits<difference_type>::max)() - k) / states;
86 max_state_count = (std::numeric_limits<difference_type>::max)();
88 max_state_count = k + states * dist;
91 template <class BidiIterator, class Allocator, class traits>
92 inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
94 // we don't know how long the sequence is:
95 max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
98 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
99 template <class BidiIterator, class Allocator, class traits>
100 inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
101 protected_proc_type proc)
103 ::boost::re_detail::concrete_protected_call
104 <perl_matcher<BidiIterator, Allocator, traits> >
106 return obj.execute();
111 template <class BidiIterator, class Allocator, class traits>
112 inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
114 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
115 return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
121 template <class BidiIterator, class Allocator, class traits>
122 bool perl_matcher<BidiIterator, Allocator, traits>::match_imp()
124 // initialise our stack if we are non-recursive:
125 #ifdef BOOST_REGEX_NON_RECURSIVE
126 save_state_init init(&m_stack_base, &m_backup_state);
127 used_block_count = BOOST_REGEX_MAX_BLOCKS;
128 #if !defined(BOOST_NO_EXCEPTIONS)
133 // reset our state machine:
137 m_match_flags |= regex_constants::match_all;
138 m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);
139 m_presult->set_base(base);
140 if(m_match_flags & match_posix)
141 m_result = *m_presult;
142 verify_options(re.flags(), m_match_flags);
143 if(0 == match_prefix())
145 return m_result[0].second == last;
147 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
151 // unwind all pushed states, apart from anything else this
152 // ensures that all the states are correctly destructed
153 // not just the memory freed.
154 while(unwind(true)){}
160 template <class BidiIterator, class Allocator, class traits>
161 inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
163 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
164 return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
170 template <class BidiIterator, class Allocator, class traits>
171 bool perl_matcher<BidiIterator, Allocator, traits>::find_imp()
173 static matcher_proc_type const s_find_vtable[7] =
175 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_any,
176 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_word,
177 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_line,
178 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf,
179 &perl_matcher<BidiIterator, Allocator, traits>::match_prefix,
180 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
181 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
184 // initialise our stack if we are non-recursive:
185 #ifdef BOOST_REGEX_NON_RECURSIVE
186 save_state_init init(&m_stack_base, &m_backup_state);
187 used_block_count = BOOST_REGEX_MAX_BLOCKS;
188 #if !defined(BOOST_NO_EXCEPTIONS)
194 if((m_match_flags & regex_constants::match_init) == 0)
196 // reset our state machine:
197 search_base = position = base;
198 pstate = re.get_first_state();
199 m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), base, last);
200 m_presult->set_base(base);
201 m_match_flags |= regex_constants::match_init;
206 search_base = position = m_result[0].second;
207 // If last match was null and match_not_null was not set then increment
208 // our start position, otherwise we go into an infinite loop:
209 if(((m_match_flags & match_not_null) == 0) && (m_result.length() == 0))
217 m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);
218 //if((base != search_base) && (base == backstop))
219 // m_match_flags |= match_prev_avail;
221 if(m_match_flags & match_posix)
223 m_result.set_size(re.mark_count(), base, last);
224 m_result.set_base(base);
227 verify_options(re.flags(), m_match_flags);
228 // find out what kind of expression we have:
229 unsigned type = (m_match_flags & match_continuous) ?
230 static_cast<unsigned int>(regbase::restart_continue)
231 : static_cast<unsigned int>(re.get_restart_type());
233 // call the appropriate search routine:
234 matcher_proc_type proc = s_find_vtable[type];
235 return (this->*proc)();
237 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
241 // unwind all pushed states, apart from anything else this
242 // ensures that all the states are correctly destructed
243 // not just the memory freed.
244 while(unwind(true)){}
250 template <class BidiIterator, class Allocator, class traits>
251 bool perl_matcher<BidiIterator, Allocator, traits>::match_prefix()
253 m_has_partial_match = false;
254 m_has_found_match = false;
255 pstate = re.get_first_state();
256 m_presult->set_first(position);
259 if(!m_has_found_match && m_has_partial_match && (m_match_flags & match_partial))
261 m_has_found_match = true;
262 m_presult->set_second(last, 0, false);
265 #ifdef BOOST_REGEX_MATCH_EXTRA
266 if(m_has_found_match && (match_extra & m_match_flags))
269 // we have a match, reverse the capture information:
271 for(unsigned i = 0; i < m_presult->size(); ++i)
273 typename sub_match<BidiIterator>::capture_sequence_type & seq = ((*m_presult)[i]).get_captures();
274 std::reverse(seq.begin(), seq.end());
278 if(!m_has_found_match)
279 position = restart; // reset search postion
280 return m_has_found_match;
283 template <class BidiIterator, class Allocator, class traits>
284 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
286 int index = static_cast<const re_brace*>(pstate)->index;
289 if((m_match_flags & match_nosubs) == 0)
290 m_presult->set_second(position, index);
292 else if((index < 0) && (index != -4))
294 // matched forward lookahead:
298 pstate = pstate->next.p;
302 template <class BidiIterator, class Allocator, class traits>
303 bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
305 unsigned int len = static_cast<const re_literal*>(pstate)->length;
306 const char_type* what = reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
308 // compare string with what we stored in
310 for(unsigned int i = 0; i < len; ++i, ++position)
312 if((position == last) || (traits_inst.translate(*position, icase) != what[i]))
315 pstate = pstate->next.p;
319 template <class BidiIterator, class Allocator, class traits>
320 bool perl_matcher<BidiIterator, Allocator, traits>::match_start_line()
322 if(position == backstop)
324 if((m_match_flags & match_prev_avail) == 0)
326 if((m_match_flags & match_not_bol) == 0)
328 pstate = pstate->next.p;
334 else if(m_match_flags & match_single_line)
337 // check the previous value character:
338 BidiIterator t(position);
342 if(is_separator(*t) && !((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n'))) )
344 pstate = pstate->next.p;
348 else if(is_separator(*t))
350 pstate = pstate->next.p;
356 template <class BidiIterator, class Allocator, class traits>
357 bool perl_matcher<BidiIterator, Allocator, traits>::match_end_line()
361 if(m_match_flags & match_single_line)
363 // we're not yet at the end so *first is always valid:
364 if(is_separator(*position))
366 if((position != backstop) || (m_match_flags & match_prev_avail))
368 // check that we're not in the middle of \r\n sequence
369 BidiIterator t(position);
371 if((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n')))
376 pstate = pstate->next.p;
380 else if((m_match_flags & match_not_eol) == 0)
382 pstate = pstate->next.p;
388 template <class BidiIterator, class Allocator, class traits>
389 bool perl_matcher<BidiIterator, Allocator, traits>::match_wild()
393 if(is_separator(*position) && ((match_any_mask & static_cast<const re_dot*>(pstate)->mask) == 0))
395 if((*position == char_type(0)) && (m_match_flags & match_not_dot_null))
397 pstate = pstate->next.p;
402 template <class BidiIterator, class Allocator, class traits>
403 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
405 if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
407 if((m_match_flags & match_all) && (position != last))
409 if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
411 m_presult->set_second(position);
413 m_has_found_match = true;
414 if((m_match_flags & match_posix) == match_posix)
416 m_result.maybe_assign(*m_presult);
417 if((m_match_flags & match_any) == 0)
420 #ifdef BOOST_REGEX_MATCH_EXTRA
421 if(match_extra & m_match_flags)
423 for(unsigned i = 0; i < m_presult->size(); ++i)
424 if((*m_presult)[i].matched)
425 ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
431 template <class BidiIterator, class Allocator, class traits>
432 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
434 bool b; // indcates whether next character is a word character
437 // prev and this character must be opposites:
438 #if defined(BOOST_REGEX_USE_C_LOCALE) && defined(__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ < 95)
439 b = traits::isctype(*position, m_word_mask);
441 b = traits_inst.isctype(*position, m_word_mask);
446 b = (m_match_flags & match_not_eow) ? true : false;
448 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
450 if(m_match_flags & match_not_bow)
458 b ^= traits_inst.isctype(*position, m_word_mask);
463 pstate = pstate->next.p;
466 return false; // no match if we get to here...
469 template <class BidiIterator, class Allocator, class traits>
470 bool perl_matcher<BidiIterator, Allocator, traits>::match_within_word()
474 // both prev and this character must be m_word_mask:
475 if(traits_inst.isctype(*position, m_word_mask))
478 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
483 b = traits_inst.isctype(*position, m_word_mask);
488 pstate = pstate->next.p;
495 template <class BidiIterator, class Allocator, class traits>
496 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_start()
499 return false; // can't be starting a word if we're already at the end of input
500 if(!traits_inst.isctype(*position, m_word_mask))
501 return false; // next character isn't a word character
502 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
504 if(m_match_flags & match_not_bow)
505 return false; // no previous input
509 // otherwise inside buffer:
510 BidiIterator t(position);
512 if(traits_inst.isctype(*t, m_word_mask))
513 return false; // previous character not non-word
515 // OK we have a match:
516 pstate = pstate->next.p;
520 template <class BidiIterator, class Allocator, class traits>
521 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_end()
523 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
524 return false; // start of buffer can't be end of word
525 BidiIterator t(position);
527 if(traits_inst.isctype(*t, m_word_mask) == false)
528 return false; // previous character wasn't a word character
532 if(m_match_flags & match_not_eow)
533 return false; // end of buffer but not end of word
537 // otherwise inside buffer:
538 if(traits_inst.isctype(*position, m_word_mask))
539 return false; // next character is a word character
541 pstate = pstate->next.p;
542 return true; // if we fall through to here then we've succeeded
545 template <class BidiIterator, class Allocator, class traits>
546 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start()
548 if((position != backstop) || (m_match_flags & match_not_bob))
551 pstate = pstate->next.p;
555 template <class BidiIterator, class Allocator, class traits>
556 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end()
558 if((position != last) || (m_match_flags & match_not_eob))
561 pstate = pstate->next.p;
565 template <class BidiIterator, class Allocator, class traits>
566 bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
569 // Compare with what we previously matched.
570 // Note that this succeeds if the backref did not partisipate
571 // in the match, this is in line with ECMAScript, but not Perl
574 BidiIterator i = (*m_presult)[static_cast<const re_brace*>(pstate)->index].first;
575 BidiIterator j = (*m_presult)[static_cast<const re_brace*>(pstate)->index].second;
578 if((position == last) || (traits_inst.translate(*position, icase) != traits_inst.translate(*i, icase)))
583 pstate = pstate->next.p;
587 template <class BidiIterator, class Allocator, class traits>
588 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set()
590 typedef typename traits::char_class_type char_class_type;
591 // let the traits class do the work:
594 BidiIterator t = re_is_set_member(position, last, static_cast<const re_set_long<char_class_type>*>(pstate), re.get_data(), icase);
597 pstate = pstate->next.p;
604 template <class BidiIterator, class Allocator, class traits>
605 bool perl_matcher<BidiIterator, Allocator, traits>::match_set()
609 if(static_cast<const re_set*>(pstate)->_map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
611 pstate = pstate->next.p;
618 template <class BidiIterator, class Allocator, class traits>
619 bool perl_matcher<BidiIterator, Allocator, traits>::match_jump()
621 pstate = static_cast<const re_jump*>(pstate)->alt.p;
625 template <class BidiIterator, class Allocator, class traits>
626 bool perl_matcher<BidiIterator, Allocator, traits>::match_combining()
630 if(is_combining(traits_inst.translate(*position, icase)))
633 while((position != last) && is_combining(traits_inst.translate(*position, icase)))
635 pstate = pstate->next.p;
639 template <class BidiIterator, class Allocator, class traits>
640 bool perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end()
642 if(m_match_flags & match_not_eob)
644 BidiIterator p(position);
645 while((p != last) && is_separator(traits_inst.translate(*p, icase)))++p;
648 pstate = pstate->next.p;
652 template <class BidiIterator, class Allocator, class traits>
653 bool perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue()
655 if(position == search_base)
657 pstate = pstate->next.p;
663 template <class BidiIterator, class Allocator, class traits>
664 bool perl_matcher<BidiIterator, Allocator, traits>::match_backstep()
667 #pragma warning(push)
668 #pragma warning(disable:4127)
670 if( ::boost::is_random_access_iterator<BidiIterator>::value)
672 std::ptrdiff_t maxlen = ::boost::re_detail::distance(backstop, position);
673 if(maxlen < static_cast<const re_brace*>(pstate)->index)
675 std::advance(position, -static_cast<const re_brace*>(pstate)->index);
679 int c = static_cast<const re_brace*>(pstate)->index;
682 if(position == backstop)
687 pstate = pstate->next.p;
694 template <class BidiIterator, class Allocator, class traits>
695 inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
697 // return true if marked sub-expression N has been matched:
698 bool result = (*m_presult)[static_cast<const re_brace*>(pstate)->index].matched;
699 pstate = pstate->next.p;
703 template <class BidiIterator, class Allocator, class traits>
704 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
706 // change our case sensitivity:
707 this->icase = static_cast<const re_case*>(pstate)->icase;
708 pstate = pstate->next.p;
713 template <class BidiIterator, class Allocator, class traits>
714 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_any()
717 #pragma warning(push)
718 #pragma warning(disable:4127)
720 const unsigned char* _map = re.get_map();
723 // skip everything we can't match:
724 while((position != last) && !can_start(*position, _map, (unsigned char)mask_any) )
728 // run out of characters, try a null match if possible:
730 return match_prefix();
733 // now try and obtain a match:
746 template <class BidiIterator, class Allocator, class traits>
747 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_word()
750 #pragma warning(push)
751 #pragma warning(disable:4127)
753 // do search optimised for word starts:
754 const unsigned char* _map = re.get_map();
755 if((m_match_flags & match_prev_avail) || (position != base))
757 else if(match_prefix())
761 while((position != last) && traits_inst.isctype(*position, m_word_mask))
763 while((position != last) && !traits_inst.isctype(*position, m_word_mask))
768 if(can_start(*position, _map, (unsigned char)mask_any) )
782 template <class BidiIterator, class Allocator, class traits>
783 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_line()
785 // do search optimised for line starts:
786 const unsigned char* _map = re.get_map();
789 while(position != last)
791 while((position != last) && !is_separator(*position))
798 if(re.can_be_null() && match_prefix())
803 if( can_start(*position, _map, (unsigned char)mask_any) )
815 template <class BidiIterator, class Allocator, class traits>
816 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf()
818 if((position == base) && ((m_match_flags & match_not_bob) == 0))
819 return match_prefix();
823 template <class BidiIterator, class Allocator, class traits>
824 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit()
828 return false; // can't possibly match if we're at the end already
830 unsigned type = (m_match_flags & match_continuous) ?
831 static_cast<unsigned int>(regbase::restart_continue)
832 : static_cast<unsigned int>(re.get_restart_type());
834 const kmp_info<char_type>* info = access::get_kmp(re);
836 const char_type* x = info->pstr;
838 while (position != last)
840 while((j > -1) && (x[j] != traits_inst.translate(*position, icase)))
841 j = info->kmp_next[j];
846 if(type == regbase::restart_fixed_lit)
848 std::advance(position, -j);
850 std::advance(restart, len);
851 m_result.set_first(position);
852 m_result.set_second(restart);
859 std::advance(position, -j);
864 for(int k = 0; (restart != position) && (k < j); ++k, --restart)
865 {} // dwa 10/20/2000 - warning suppression for MWCW
869 j = 0; //we could do better than this...
874 if((m_match_flags & match_partial) && (position == last) && j)
876 // we need to check for a partial match:
878 std::advance(position, -j);
879 return match_prefix();
885 } // namespace re_detail
892 #ifdef BOOST_HAS_ABI_HEADERS
893 # include BOOST_ABI_SUFFIX