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*)
81 // How many states should we allow our machine to visit before giving up?
82 // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)
83 // where N is the length of the string, and S is the number of states
84 // in the machine. It's tempting to up this to O(N^2S) or even O(N^2S^2)
85 // but these take unreasonably amounts of time to bale out in pathological
88 // Calculate NS^2 first:
90 static const boost::uintmax_t k = 100000;
91 boost::uintmax_t dist = boost::re_detail::distance(base, last);
94 boost::uintmax_t states = re.size();
98 if((std::numeric_limits<boost::uintmax_t>::max)() / dist < states)
100 max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;
104 if((std::numeric_limits<boost::uintmax_t>::max)() - k < states)
106 max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;
111 max_state_count = states;
114 // Now calculate N^2:
117 if((std::numeric_limits<boost::uintmax_t>::max)() / dist < states)
119 max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;
123 if((std::numeric_limits<boost::uintmax_t>::max)() - k < states)
125 max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;
130 // N^2 can be a very large number indeed, to prevent things getting out
131 // of control, cap the max states:
133 if(states > BOOST_REGEX_MAX_STATE_COUNT)
134 states = BOOST_REGEX_MAX_STATE_COUNT;
136 // If (the possibly capped) N^2 is larger than our first estimate,
139 if(states > max_state_count)
140 max_state_count = states;
143 template <class BidiIterator, class Allocator, class traits>
144 inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
146 // we don't know how long the sequence is:
147 max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
150 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
151 template <class BidiIterator, class Allocator, class traits>
152 inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
153 protected_proc_type proc)
155 ::boost::re_detail::concrete_protected_call
156 <perl_matcher<BidiIterator, Allocator, traits> >
158 return obj.execute();
163 template <class BidiIterator, class Allocator, class traits>
164 inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
166 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
167 return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
173 template <class BidiIterator, class Allocator, class traits>
174 bool perl_matcher<BidiIterator, Allocator, traits>::match_imp()
176 // initialise our stack if we are non-recursive:
177 #ifdef BOOST_REGEX_NON_RECURSIVE
178 save_state_init init(&m_stack_base, &m_backup_state);
179 used_block_count = BOOST_REGEX_MAX_BLOCKS;
180 #if !defined(BOOST_NO_EXCEPTIONS)
185 // reset our state machine:
189 m_match_flags |= regex_constants::match_all;
190 m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);
191 m_presult->set_base(base);
192 if(m_match_flags & match_posix)
193 m_result = *m_presult;
194 verify_options(re.flags(), m_match_flags);
195 if(0 == match_prefix())
197 return m_result[0].second == last;
199 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
203 // unwind all pushed states, apart from anything else this
204 // ensures that all the states are correctly destructed
205 // not just the memory freed.
206 while(unwind(true)){}
212 template <class BidiIterator, class Allocator, class traits>
213 inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
215 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
216 return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
222 template <class BidiIterator, class Allocator, class traits>
223 bool perl_matcher<BidiIterator, Allocator, traits>::find_imp()
225 static matcher_proc_type const s_find_vtable[7] =
227 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_any,
228 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_word,
229 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_line,
230 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf,
231 &perl_matcher<BidiIterator, Allocator, traits>::match_prefix,
232 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
233 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
236 // initialise our stack if we are non-recursive:
237 #ifdef BOOST_REGEX_NON_RECURSIVE
238 save_state_init init(&m_stack_base, &m_backup_state);
239 used_block_count = BOOST_REGEX_MAX_BLOCKS;
240 #if !defined(BOOST_NO_EXCEPTIONS)
246 if((m_match_flags & regex_constants::match_init) == 0)
248 // reset our state machine:
249 search_base = position = base;
250 pstate = re.get_first_state();
251 m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), base, last);
252 m_presult->set_base(base);
253 m_match_flags |= regex_constants::match_init;
258 search_base = position = m_result[0].second;
259 // If last match was null and match_not_null was not set then increment
260 // our start position, otherwise we go into an infinite loop:
261 if(((m_match_flags & match_not_null) == 0) && (m_result.length() == 0))
269 m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);
270 //if((base != search_base) && (base == backstop))
271 // m_match_flags |= match_prev_avail;
273 if(m_match_flags & match_posix)
275 m_result.set_size(re.mark_count(), base, last);
276 m_result.set_base(base);
279 verify_options(re.flags(), m_match_flags);
280 // find out what kind of expression we have:
281 unsigned type = (m_match_flags & match_continuous) ?
282 static_cast<unsigned int>(regbase::restart_continue)
283 : static_cast<unsigned int>(re.get_restart_type());
285 // call the appropriate search routine:
286 matcher_proc_type proc = s_find_vtable[type];
287 return (this->*proc)();
289 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
293 // unwind all pushed states, apart from anything else this
294 // ensures that all the states are correctly destructed
295 // not just the memory freed.
296 while(unwind(true)){}
302 template <class BidiIterator, class Allocator, class traits>
303 bool perl_matcher<BidiIterator, Allocator, traits>::match_prefix()
305 m_has_partial_match = false;
306 m_has_found_match = false;
307 pstate = re.get_first_state();
308 m_presult->set_first(position);
311 if(!m_has_found_match && m_has_partial_match && (m_match_flags & match_partial))
313 m_has_found_match = true;
314 m_presult->set_second(last, 0, false);
317 #ifdef BOOST_REGEX_MATCH_EXTRA
318 if(m_has_found_match && (match_extra & m_match_flags))
321 // we have a match, reverse the capture information:
323 for(unsigned i = 0; i < m_presult->size(); ++i)
325 typename sub_match<BidiIterator>::capture_sequence_type & seq = ((*m_presult)[i]).get_captures();
326 std::reverse(seq.begin(), seq.end());
330 if(!m_has_found_match)
331 position = restart; // reset search postion
332 return m_has_found_match;
335 template <class BidiIterator, class Allocator, class traits>
336 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
338 int index = static_cast<const re_brace*>(pstate)->index;
341 if((m_match_flags & match_nosubs) == 0)
342 m_presult->set_second(position, index);
344 else if((index < 0) && (index != -4))
346 // matched forward lookahead:
350 pstate = pstate->next.p;
354 template <class BidiIterator, class Allocator, class traits>
355 bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
357 unsigned int len = static_cast<const re_literal*>(pstate)->length;
358 const char_type* what = reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
360 // compare string with what we stored in
362 for(unsigned int i = 0; i < len; ++i, ++position)
364 if((position == last) || (traits_inst.translate(*position, icase) != what[i]))
367 pstate = pstate->next.p;
371 template <class BidiIterator, class Allocator, class traits>
372 bool perl_matcher<BidiIterator, Allocator, traits>::match_start_line()
374 if(position == backstop)
376 if((m_match_flags & match_prev_avail) == 0)
378 if((m_match_flags & match_not_bol) == 0)
380 pstate = pstate->next.p;
386 else if(m_match_flags & match_single_line)
389 // check the previous value character:
390 BidiIterator t(position);
394 if(is_separator(*t) && !((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n'))) )
396 pstate = pstate->next.p;
400 else if(is_separator(*t))
402 pstate = pstate->next.p;
408 template <class BidiIterator, class Allocator, class traits>
409 bool perl_matcher<BidiIterator, Allocator, traits>::match_end_line()
413 if(m_match_flags & match_single_line)
415 // we're not yet at the end so *first is always valid:
416 if(is_separator(*position))
418 if((position != backstop) || (m_match_flags & match_prev_avail))
420 // check that we're not in the middle of \r\n sequence
421 BidiIterator t(position);
423 if((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n')))
428 pstate = pstate->next.p;
432 else if((m_match_flags & match_not_eol) == 0)
434 pstate = pstate->next.p;
440 template <class BidiIterator, class Allocator, class traits>
441 bool perl_matcher<BidiIterator, Allocator, traits>::match_wild()
445 if(is_separator(*position) && ((match_any_mask & static_cast<const re_dot*>(pstate)->mask) == 0))
447 if((*position == char_type(0)) && (m_match_flags & match_not_dot_null))
449 pstate = pstate->next.p;
454 template <class BidiIterator, class Allocator, class traits>
455 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
457 if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
459 if((m_match_flags & match_all) && (position != last))
461 if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
463 m_presult->set_second(position);
465 m_has_found_match = true;
466 if((m_match_flags & match_posix) == match_posix)
468 m_result.maybe_assign(*m_presult);
469 if((m_match_flags & match_any) == 0)
472 #ifdef BOOST_REGEX_MATCH_EXTRA
473 if(match_extra & m_match_flags)
475 for(unsigned i = 0; i < m_presult->size(); ++i)
476 if((*m_presult)[i].matched)
477 ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
483 template <class BidiIterator, class Allocator, class traits>
484 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
486 bool b; // indcates whether next character is a word character
489 // prev and this character must be opposites:
490 #if defined(BOOST_REGEX_USE_C_LOCALE) && defined(__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ < 95)
491 b = traits::isctype(*position, m_word_mask);
493 b = traits_inst.isctype(*position, m_word_mask);
498 b = (m_match_flags & match_not_eow) ? true : false;
500 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
502 if(m_match_flags & match_not_bow)
510 b ^= traits_inst.isctype(*position, m_word_mask);
515 pstate = pstate->next.p;
518 return false; // no match if we get to here...
521 template <class BidiIterator, class Allocator, class traits>
522 bool perl_matcher<BidiIterator, Allocator, traits>::match_within_word()
526 // both prev and this character must be m_word_mask:
527 if(traits_inst.isctype(*position, m_word_mask))
530 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
535 b = traits_inst.isctype(*position, m_word_mask);
540 pstate = pstate->next.p;
547 template <class BidiIterator, class Allocator, class traits>
548 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_start()
551 return false; // can't be starting a word if we're already at the end of input
552 if(!traits_inst.isctype(*position, m_word_mask))
553 return false; // next character isn't a word character
554 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
556 if(m_match_flags & match_not_bow)
557 return false; // no previous input
561 // otherwise inside buffer:
562 BidiIterator t(position);
564 if(traits_inst.isctype(*t, m_word_mask))
565 return false; // previous character not non-word
567 // OK we have a match:
568 pstate = pstate->next.p;
572 template <class BidiIterator, class Allocator, class traits>
573 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_end()
575 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
576 return false; // start of buffer can't be end of word
577 BidiIterator t(position);
579 if(traits_inst.isctype(*t, m_word_mask) == false)
580 return false; // previous character wasn't a word character
584 if(m_match_flags & match_not_eow)
585 return false; // end of buffer but not end of word
589 // otherwise inside buffer:
590 if(traits_inst.isctype(*position, m_word_mask))
591 return false; // next character is a word character
593 pstate = pstate->next.p;
594 return true; // if we fall through to here then we've succeeded
597 template <class BidiIterator, class Allocator, class traits>
598 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start()
600 if((position != backstop) || (m_match_flags & match_not_bob))
603 pstate = pstate->next.p;
607 template <class BidiIterator, class Allocator, class traits>
608 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end()
610 if((position != last) || (m_match_flags & match_not_eob))
613 pstate = pstate->next.p;
617 template <class BidiIterator, class Allocator, class traits>
618 bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
621 // Compare with what we previously matched.
622 // Note that this succeeds if the backref did not partisipate
623 // in the match, this is in line with ECMAScript, but not Perl
626 BidiIterator i = (*m_presult)[static_cast<const re_brace*>(pstate)->index].first;
627 BidiIterator j = (*m_presult)[static_cast<const re_brace*>(pstate)->index].second;
630 if((position == last) || (traits_inst.translate(*position, icase) != traits_inst.translate(*i, icase)))
635 pstate = pstate->next.p;
639 template <class BidiIterator, class Allocator, class traits>
640 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set()
642 typedef typename traits::char_class_type char_class_type;
643 // let the traits class do the work:
646 BidiIterator t = re_is_set_member(position, last, static_cast<const re_set_long<char_class_type>*>(pstate), re.get_data(), icase);
649 pstate = pstate->next.p;
656 template <class BidiIterator, class Allocator, class traits>
657 bool perl_matcher<BidiIterator, Allocator, traits>::match_set()
661 if(static_cast<const re_set*>(pstate)->_map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
663 pstate = pstate->next.p;
670 template <class BidiIterator, class Allocator, class traits>
671 bool perl_matcher<BidiIterator, Allocator, traits>::match_jump()
673 pstate = static_cast<const re_jump*>(pstate)->alt.p;
677 template <class BidiIterator, class Allocator, class traits>
678 bool perl_matcher<BidiIterator, Allocator, traits>::match_combining()
682 if(is_combining(traits_inst.translate(*position, icase)))
685 while((position != last) && is_combining(traits_inst.translate(*position, icase)))
687 pstate = pstate->next.p;
691 template <class BidiIterator, class Allocator, class traits>
692 bool perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end()
694 if(m_match_flags & match_not_eob)
696 BidiIterator p(position);
697 while((p != last) && is_separator(traits_inst.translate(*p, icase)))++p;
700 pstate = pstate->next.p;
704 template <class BidiIterator, class Allocator, class traits>
705 bool perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue()
707 if(position == search_base)
709 pstate = pstate->next.p;
715 template <class BidiIterator, class Allocator, class traits>
716 bool perl_matcher<BidiIterator, Allocator, traits>::match_backstep()
719 #pragma warning(push)
720 #pragma warning(disable:4127)
722 if( ::boost::is_random_access_iterator<BidiIterator>::value)
724 std::ptrdiff_t maxlen = ::boost::re_detail::distance(backstop, position);
725 if(maxlen < static_cast<const re_brace*>(pstate)->index)
727 std::advance(position, -static_cast<const re_brace*>(pstate)->index);
731 int c = static_cast<const re_brace*>(pstate)->index;
734 if(position == backstop)
739 pstate = pstate->next.p;
746 template <class BidiIterator, class Allocator, class traits>
747 inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
749 // return true if marked sub-expression N has been matched:
750 bool result = (*m_presult)[static_cast<const re_brace*>(pstate)->index].matched;
751 pstate = pstate->next.p;
755 template <class BidiIterator, class Allocator, class traits>
756 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
758 // change our case sensitivity:
759 this->icase = static_cast<const re_case*>(pstate)->icase;
760 pstate = pstate->next.p;
765 template <class BidiIterator, class Allocator, class traits>
766 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_any()
769 #pragma warning(push)
770 #pragma warning(disable:4127)
772 const unsigned char* _map = re.get_map();
775 // skip everything we can't match:
776 while((position != last) && !can_start(*position, _map, (unsigned char)mask_any) )
780 // run out of characters, try a null match if possible:
782 return match_prefix();
785 // now try and obtain a match:
798 template <class BidiIterator, class Allocator, class traits>
799 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_word()
802 #pragma warning(push)
803 #pragma warning(disable:4127)
805 // do search optimised for word starts:
806 const unsigned char* _map = re.get_map();
807 if((m_match_flags & match_prev_avail) || (position != base))
809 else if(match_prefix())
813 while((position != last) && traits_inst.isctype(*position, m_word_mask))
815 while((position != last) && !traits_inst.isctype(*position, m_word_mask))
820 if(can_start(*position, _map, (unsigned char)mask_any) )
834 template <class BidiIterator, class Allocator, class traits>
835 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_line()
837 // do search optimised for line starts:
838 const unsigned char* _map = re.get_map();
841 while(position != last)
843 while((position != last) && !is_separator(*position))
850 if(re.can_be_null() && match_prefix())
855 if( can_start(*position, _map, (unsigned char)mask_any) )
867 template <class BidiIterator, class Allocator, class traits>
868 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf()
870 if((position == base) && ((m_match_flags & match_not_bob) == 0))
871 return match_prefix();
875 template <class BidiIterator, class Allocator, class traits>
876 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit()
880 return false; // can't possibly match if we're at the end already
882 unsigned type = (m_match_flags & match_continuous) ?
883 static_cast<unsigned int>(regbase::restart_continue)
884 : static_cast<unsigned int>(re.get_restart_type());
886 const kmp_info<char_type>* info = access::get_kmp(re);
888 const char_type* x = info->pstr;
890 while (position != last)
892 while((j > -1) && (x[j] != traits_inst.translate(*position, icase)))
893 j = info->kmp_next[j];
898 if(type == regbase::restart_fixed_lit)
900 std::advance(position, -j);
902 std::advance(restart, len);
903 m_result.set_first(position);
904 m_result.set_second(restart);
911 std::advance(position, -j);
916 for(int k = 0; (restart != position) && (k < j); ++k, --restart)
917 {} // dwa 10/20/2000 - warning suppression for MWCW
921 j = 0; //we could do better than this...
926 if((m_match_flags & match_partial) && (position == last) && j)
928 // we need to check for a partial match:
930 std::advance(position, -j);
931 return match_prefix();
937 } // namespace re_detail
944 #ifdef BOOST_HAS_ABI_HEADERS
945 # include BOOST_ABI_SUFFIX