#ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
#define BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable: 4103)
+#endif
#ifdef BOOST_HAS_ABI_HEADERS
# include BOOST_ABI_PREFIX
#endif
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
#ifdef __BORLANDC__
# pragma option push -w-8008 -w-8066
#endif
+#ifdef BOOST_MSVC
+# pragma warning(push)
+# pragma warning(disable: 4800)
+#endif
namespace boost{
namespace re_detail{
-template <class BidiIterator, class Allocator, class traits>
-perl_matcher<BidiIterator, Allocator, traits>::perl_matcher(BidiIterator first, BidiIterator end,
- match_results<BidiIterator, Allocator>& what,
- const basic_regex<char_type, traits>& e,
- match_flag_type f,
- BidiIterator b)
- : m_result(what), base(first), last(end),
- position(first), backstop(b), re(e), traits_inst(e.get_traits()),
- m_independent(false), next_count(&rep_obj), rep_obj(&next_count)
-{
- construct_init(e, f);
-}
-
template <class BidiIterator, class Allocator, class traits>
void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)
{
typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;
+ typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;
if(e.empty())
{
}
pstate = 0;
m_match_flags = f;
- icase = re.flags() & regex_constants::icase;
estimate_max_state_count(static_cast<category*>(0));
+ expression_flag_type re_f = re.flags();
+ icase = re_f & regex_constants::icase;
if(!(m_match_flags & (match_perl|match_posix)))
{
- if((re.flags() & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
+ if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
m_match_flags |= match_perl;
- else if((re.flags() & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
+ else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
m_match_flags |= match_perl;
else
m_match_flags |= match_posix;
m_backup_state = 0;
#endif
// find the value to use for matching word boundaries:
- const char_type w = static_cast<char_type>('w');
- m_word_mask = traits_inst.lookup_classname(&w, &w+1);
+ m_word_mask = re.get_data().m_word_mask;
// find bitmask to use for matching '.':
match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? re_detail::test_not_newline : re_detail::test_newline);
}
template <class BidiIterator, class Allocator, class traits>
void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)
{
- static const difference_type k = 100000;
- difference_type dist = boost::re_detail::distance(base, last);
- traits_size_type states = static_cast<traits_size_type>(re.size());
+ //
+ // How many states should we allow our machine to visit before giving up?
+ // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)
+ // where N is the length of the string, and S is the number of states
+ // in the machine. It's tempting to up this to O(N^2S) or even O(N^2S^2)
+ // but these take unreasonably amounts of time to bale out in pathological
+ // cases.
+ //
+ // Calculate NS^2 first:
+ //
+ static const std::ptrdiff_t k = 100000;
+ std::ptrdiff_t dist = boost::re_detail::distance(base, last);
+ if(dist == 0)
+ dist = 1;
+ std::ptrdiff_t states = re.size();
+ if(states == 0)
+ states = 1;
states *= states;
- difference_type lim = ((std::numeric_limits<difference_type>::max)() - k) / states;
- if(dist >= lim)
- max_state_count = (std::numeric_limits<difference_type>::max)();
- else
- max_state_count = k + states * dist;
+ if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
+ {
+ max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
+ return;
+ }
+ states *= dist;
+ if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
+ {
+ max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
+ return;
+ }
+ states += k;
+
+ max_state_count = states;
+
+ //
+ // Now calculate N^2:
+ //
+ states = dist;
+ if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
+ {
+ max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
+ return;
+ }
+ states *= dist;
+ if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
+ {
+ max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
+ return;
+ }
+ states += k;
+ //
+ // N^2 can be a very large number indeed, to prevent things getting out
+ // of control, cap the max states:
+ //
+ if(states > BOOST_REGEX_MAX_STATE_COUNT)
+ states = BOOST_REGEX_MAX_STATE_COUNT;
+ //
+ // If (the possibly capped) N^2 is larger than our first estimate,
+ // use this instead:
+ //
+ if(states > max_state_count)
+ max_state_count = states;
}
template <class BidiIterator, class Allocator, class traits>
-void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
+inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
{
// we don't know how long the sequence is:
max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
template <class BidiIterator, class Allocator, class traits>
-bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
+inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
protected_proc_type proc)
{
- /*
- __try{
- return (this->*proc)();
- }__except(EXCEPTION_STACK_OVERFLOW == GetExceptionCode())
- {
- reset_stack_guard_page();
- }
- // we only get here after a stack overflow:
- raise_error<traits>(traits_inst, regex_constants::error_size);
- // and we never really get here at all:
- return false;
- */
::boost::re_detail::concrete_protected_call
<perl_matcher<BidiIterator, Allocator, traits> >
obj(this, proc);
#endif
template <class BidiIterator, class Allocator, class traits>
-bool perl_matcher<BidiIterator, Allocator, traits>::match()
+inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
{
#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
m_match_flags |= regex_constants::match_all;
m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);
m_presult->set_base(base);
+ m_presult->set_named_subs(this->re.get_named_subs());
if(m_match_flags & match_posix)
m_result = *m_presult;
verify_options(re.flags(), m_match_flags);
if(0 == match_prefix())
return false;
- return m_result[0].second == last;
+ return (m_result[0].second == last) && (m_result[0].first == base);
#if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
}
}
template <class BidiIterator, class Allocator, class traits>
-bool perl_matcher<BidiIterator, Allocator, traits>::find()
+inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
{
#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
pstate = re.get_first_state();
m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), base, last);
m_presult->set_base(base);
+ m_presult->set_named_subs(this->re.get_named_subs());
m_match_flags |= regex_constants::match_init;
}
else
return m_has_found_match;
}
-template <class BidiIterator, class Allocator, class traits>
-bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
-{
- int index = static_cast<const re_brace*>(pstate)->index;
- if(index > 0)
- {
- if((m_match_flags & match_nosubs) == 0)
- m_presult->set_second(position, index);
- }
- else if((index < 0) && (index != -4))
- {
- // matched forward lookahead:
- pstate = 0;
- return true;
- }
- pstate = pstate->next.p;
- return true;
-}
-
template <class BidiIterator, class Allocator, class traits>
bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
{
return true;
}
-template <class BidiIterator, class Allocator, class traits>
-bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
-{
- if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
- return false;
- if((m_match_flags & match_all) && (position != last))
- return false;
- if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
- return false;
- m_presult->set_second(position);
- pstate = 0;
- m_has_found_match = true;
- if((m_match_flags & match_posix) == match_posix)
- {
- m_result.maybe_assign(*m_presult);
- if((m_match_flags & match_any) == 0)
- return false;
- }
-#ifdef BOOST_REGEX_MATCH_EXTRA
- if(match_extra & m_match_flags)
- {
- for(unsigned i = 0; i < m_presult->size(); ++i)
- if((*m_presult)[i].matched)
- ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
- }
-#endif
- return true;
-}
-
template <class BidiIterator, class Allocator, class traits>
bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
{
if(position == last)
return false;
// both prev and this character must be m_word_mask:
- if(traits_inst.isctype(*position, m_word_mask))
+ bool prev = traits_inst.isctype(*position, m_word_mask);
{
bool b;
if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
b = traits_inst.isctype(*position, m_word_mask);
++position;
}
- if(b)
+ if(b == prev)
{
pstate = pstate->next.p;
return true;
template <class BidiIterator, class Allocator, class traits>
bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
{
- // compare with what we previously matched:
- BidiIterator i = (*m_presult)[static_cast<const re_brace*>(pstate)->index].first;
- BidiIterator j = (*m_presult)[static_cast<const re_brace*>(pstate)->index].second;
+ //
+ // Compare with what we previously matched.
+ // Note that this succeeds if the backref did not partisipate
+ // in the match, this is in line with ECMAScript, but not Perl
+ // or PCRE.
+ //
+ int index = static_cast<const re_brace*>(pstate)->index;
+ if(index >= 10000)
+ {
+ named_subexpressions::range_type r = re.get_data().equal_range(index);
+ BOOST_ASSERT(r.first != r.second);
+ do
+ {
+ index = r.first->index;
+ ++r.first;
+ }while((r.first != r.second) && ((*m_presult)[index].matched != true));
+ }
+
+ if((m_match_flags & match_perl) && !(*m_presult)[index].matched)
+ return false;
+
+ BidiIterator i = (*m_presult)[index].first;
+ BidiIterator j = (*m_presult)[index].second;
while(i != j)
{
if((position == last) || (traits_inst.translate(*position, icase) != traits_inst.translate(*i, icase)))
inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
{
// return true if marked sub-expression N has been matched:
- bool result = (*m_presult)[static_cast<const re_brace*>(pstate)->index].matched;
- pstate = pstate->next.p;
+ int index = static_cast<const re_brace*>(pstate)->index;
+ bool result = false;
+ if(index == 9999)
+ {
+ // Magic value for a (DEFINE) block:
+ return false;
+ }
+ else if(index > 0)
+ {
+ // Have we matched subexpression "index"?
+ // Check if index is a hash value:
+ if(index >= 10000)
+ {
+ named_subexpressions::range_type r = re.get_data().equal_range(index);
+ while(r.first != r.second)
+ {
+ if((*m_presult)[r.first->index].matched)
+ {
+ result = true;
+ break;
+ }
+ ++r.first;
+ }
+ }
+ else
+ {
+ result = (*m_presult)[index].matched;
+ }
+ pstate = pstate->next.p;
+ }
+ else
+ {
+ // Have we recursed into subexpression "index"?
+ // If index == 0 then check for any recursion at all, otherwise for recursion to -index-1.
+ int idx = -index-1;
+ if(idx >= 10000)
+ {
+ named_subexpressions::range_type r = re.get_data().equal_range(idx);
+ int stack_index = recursion_stack.empty() ? -1 : recursion_stack.back().idx;
+ while(r.first != r.second)
+ {
+ result |= (stack_index == r.first->index);
+ if(result)break;
+ ++r.first;
+ }
+ }
+ else
+ {
+ result = !recursion_stack.empty() && ((recursion_stack.back().idx == idx) || (index == 0));
+ }
+ pstate = pstate->next.p;
+ }
return result;
}
} // namespace boost
+#ifdef BOOST_MSVC
+# pragma warning(pop)
+#endif
+
#ifdef __BORLANDC__
# pragma option pop
#endif
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable: 4103)
+#endif
#ifdef BOOST_HAS_ABI_HEADERS
# include BOOST_ABI_SUFFIX
#endif
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
#endif
projects / lyx.git / blobdiff