regex/v4/perl_matcher_common.hpp

0001 /*
0002  *
0003  * Copyright (c) 2002
0004  * John Maddock
0005  *
0006  * Use, modification and distribution are subject to the
0007  * Boost Software License, Version 1.0. (See accompanying file
0008  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0009  *
0010  */
0011
0012  /*
0013   *   LOCATION:    see http://www.boost.org for most recent version.
0014   *   FILE         perl_matcher_common.cpp
0015   *   VERSION      see <boost/version.hpp>
0016   *   DESCRIPTION: Definitions of perl_matcher member functions that are
0017   *                common to both the recursive and non-recursive versions.
0018   */
0019
0020 #ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
0021 #define BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
0022
0023 #ifdef BOOST_MSVC
0024 #pragma warning(push)
0025 #pragma warning(disable: 4103)
0026 #if BOOST_MSVC >= 1800
0027 #pragma warning(disable: 26812)
0028 #endif
0029 #endif
0030 #ifdef BOOST_HAS_ABI_HEADERS
0031 #  include BOOST_ABI_PREFIX
0032 #endif
0033 #ifdef BOOST_MSVC
0034 #pragma warning(pop)
0035 #endif
0036
0037 #ifdef BOOST_BORLANDC
0038 #  pragma option push -w-8008 -w-8066
0039 #endif
0040 #ifdef BOOST_MSVC
0041 #  pragma warning(push)
0042 #if BOOST_MSVC < 1910
0043 #pragma warning(disable:4800)
0044 #endif
0045 #endif
0046
0047 namespace boost{
0048 namespace BOOST_REGEX_DETAIL_NS{
0049
0050 #ifdef BOOST_MSVC
0051 #  pragma warning(push)
0052 #pragma warning(disable:26812)
0053 #endif
0054    template <class BidiIterator, class Allocator, class traits>
0055 void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)
0056 {
0057    typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;
0058    typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;
0059
0060    if(e.empty())
0061    {
0062       // precondition failure: e is not a valid regex.
0063       std::invalid_argument ex("Invalid regular expression object");
0064       boost::throw_exception(ex);
0065    }
0066    pstate = 0;
0067    m_match_flags = f;
0068    estimate_max_state_count(static_cast<category*>(0));
0069    expression_flag_type re_f = re.flags();
0070    icase = re_f & regex_constants::icase;
0071    if(!(m_match_flags & (match_perl|match_posix)))
0072    {
0073       if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
0074          m_match_flags |= match_perl;
0075       else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
0076          m_match_flags |= match_perl;
0077       else if((re_f & (regbase::main_option_type|regbase::literal)) == (regbase::literal))
0078          m_match_flags |= match_perl;
0079       else
0080          m_match_flags |= match_posix;
0081    }
0082    if(m_match_flags & match_posix)
0083    {
0084       m_temp_match.reset(new match_results<BidiIterator, Allocator>());
0085       m_presult = m_temp_match.get();
0086    }
0087    else
0088       m_presult = &m_result;
0089 #ifdef BOOST_REGEX_NON_RECURSIVE
0090    m_stack_base = 0;
0091    m_backup_state = 0;
0092 #elif defined(BOOST_REGEX_RECURSIVE)
0093    m_can_backtrack = true;
0094    m_have_accept = false;
0095 #endif
0096    // find the value to use for matching word boundaries:
0097    m_word_mask = re.get_data().m_word_mask;
0098    // find bitmask to use for matching '.':
0099    match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? BOOST_REGEX_DETAIL_NS::test_not_newline : BOOST_REGEX_DETAIL_NS::test_newline);
0100    // Disable match_any if requested in the state machine:
0101    if(e.get_data().m_disable_match_any)
0102       m_match_flags &= regex_constants::match_not_any;
0103 }
0104 #ifdef BOOST_MSVC
0105 #  pragma warning(pop)
0106 #endif
0107
0108 template <class BidiIterator, class Allocator, class traits>
0109 void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)
0110 {
0111    //
0112    // How many states should we allow our machine to visit before giving up?
0113    // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)
0114    // where N is the length of the string, and S is the number of states
0115    // in the machine.  It's tempting to up this to O(N^2S) or even O(N^2S^2)
0116    // but these take unreasonably amounts of time to bale out in pathological
0117    // cases.
0118    //
0119    // Calculate NS^2 first:
0120    //
0121    static const std::ptrdiff_t k = 100000;
0122    std::ptrdiff_t dist = boost::BOOST_REGEX_DETAIL_NS::distance(base, last);
0123    if(dist == 0)
0124       dist = 1;
0125    std::ptrdiff_t states = re.size();
0126    if(states == 0)
0127       states = 1;
0128    if ((std::numeric_limits<std::ptrdiff_t>::max)() / states < states)
0129    {
0130       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
0131       return;
0132    }
0133    states *= states;
0134    if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
0135    {
0136       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
0137       return;
0138    }
0139    states *= dist;
0140    if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
0141    {
0142       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
0143       return;
0144    }
0145    states += k;
0146
0147    max_state_count = states;
0148
0149    //
0150    // Now calculate N^2:
0151    //
0152    states = dist;
0153    if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
0154    {
0155       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
0156       return;
0157    }
0158    states *= dist;
0159    if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
0160    {
0161       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
0162       return;
0163    }
0164    states += k;
0165    //
0166    // N^2 can be a very large number indeed, to prevent things getting out
0167    // of control, cap the max states:
0168    //
0169    if(states > BOOST_REGEX_MAX_STATE_COUNT)
0170       states = BOOST_REGEX_MAX_STATE_COUNT;
0171    //
0172    // If (the possibly capped) N^2 is larger than our first estimate,
0173    // use this instead:
0174    //
0175    if(states > max_state_count)
0176       max_state_count = states;
0177 }
0178
0179 template <class BidiIterator, class Allocator, class traits>
0180 inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
0181 {
0182    // we don't know how long the sequence is:
0183    max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
0184 }
0185
0186 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
0187 template <class BidiIterator, class Allocator, class traits>
0188 inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
0189    protected_proc_type proc)
0190 {
0191    ::boost::BOOST_REGEX_DETAIL_NS::concrete_protected_call
0192       <perl_matcher<BidiIterator, Allocator, traits> >
0193       obj(this, proc);
0194    return obj.execute();
0195
0196 }
0197 #endif
0198
0199 template <class BidiIterator, class Allocator, class traits>
0200 inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
0201 {
0202 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
0203    return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
0204 #else
0205    return match_imp();
0206 #endif
0207 }
0208
0209 template <class BidiIterator, class Allocator, class traits>
0210 bool perl_matcher<BidiIterator, Allocator, traits>::match_imp()
0211 {
0212    // initialise our stack if we are non-recursive:
0213 #ifdef BOOST_REGEX_NON_RECURSIVE
0214    save_state_init init(&m_stack_base, &m_backup_state);
0215    used_block_count = BOOST_REGEX_MAX_BLOCKS;
0216 #if !defined(BOOST_NO_EXCEPTIONS)
0217    try{
0218 #endif
0219 #endif
0220
0221    // reset our state machine:
0222    position = base;
0223    search_base = base;
0224    state_count = 0;
0225    m_match_flags |= regex_constants::match_all;
0226    m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), search_base, last);
0227    m_presult->set_base(base);
0228    m_presult->set_named_subs(this->re.get_named_subs());
0229    if(m_match_flags & match_posix)
0230       m_result = *m_presult;
0231    verify_options(re.flags(), m_match_flags);
0232    if(0 == match_prefix())
0233       return false;
0234    return (m_result[0].second == last) && (m_result[0].first == base);
0235
0236 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
0237    }
0238    catch(...)
0239    {
0240       // unwind all pushed states, apart from anything else this
0241       // ensures that all the states are correctly destructed
0242       // not just the memory freed.
0243       while(unwind(true)){}
0244       throw;
0245    }
0246 #endif
0247 }
0248
0249 template <class BidiIterator, class Allocator, class traits>
0250 inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
0251 {
0252 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
0253    return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
0254 #else
0255    return find_imp();
0256 #endif
0257 }
0258
0259 template <class BidiIterator, class Allocator, class traits>
0260 bool perl_matcher<BidiIterator, Allocator, traits>::find_imp()
0261 {
0262    static matcher_proc_type const s_find_vtable[7] =
0263    {
0264       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_any,
0265       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_word,
0266       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_line,
0267       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf,
0268       &perl_matcher<BidiIterator, Allocator, traits>::match_prefix,
0269       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
0270       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
0271    };
0272
0273    // initialise our stack if we are non-recursive:
0274 #ifdef BOOST_REGEX_NON_RECURSIVE
0275    save_state_init init(&m_stack_base, &m_backup_state);
0276    used_block_count = BOOST_REGEX_MAX_BLOCKS;
0277 #if !defined(BOOST_NO_EXCEPTIONS)
0278    try{
0279 #endif
0280 #endif
0281
0282    state_count = 0;
0283    if((m_match_flags & regex_constants::match_init) == 0)
0284    {
0285       // reset our state machine:
0286       search_base = position = base;
0287       pstate = re.get_first_state();
0288       m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), base, last);
0289       m_presult->set_base(base);
0290       m_presult->set_named_subs(this->re.get_named_subs());
0291       m_match_flags |= regex_constants::match_init;
0292    }
0293    else
0294    {
0295       // start again:
0296       search_base = position = m_result[0].second;
0297       // If last match was null and match_not_null was not set then increment
0298       // our start position, otherwise we go into an infinite loop:
0299       if(((m_match_flags & match_not_null) == 0) && (m_result.length() == 0))
0300       {
0301          if(position == last)
0302             return false;
0303          else
0304             ++position;
0305       }
0306       // reset $` start:
0307       m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), search_base, last);
0308       //if((base != search_base) && (base == backstop))
0309       //   m_match_flags |= match_prev_avail;
0310    }
0311    if(m_match_flags & match_posix)
0312    {
0313       m_result.set_size(static_cast<typename results_type::size_type>(1u + re.mark_count()), base, last);
0314       m_result.set_base(base);
0315    }
0316
0317    verify_options(re.flags(), m_match_flags);
0318    // find out what kind of expression we have:
0319    unsigned type = (m_match_flags & match_continuous) ?
0320       static_cast<unsigned int>(regbase::restart_continue)
0321          : static_cast<unsigned int>(re.get_restart_type());
0322
0323    // call the appropriate search routine:
0324    matcher_proc_type proc = s_find_vtable[type];
0325    return (this->*proc)();
0326
0327 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
0328    }
0329    catch(...)
0330    {
0331       // unwind all pushed states, apart from anything else this
0332       // ensures that all the states are correctly destructed
0333       // not just the memory freed.
0334       while(unwind(true)){}
0335       throw;
0336    }
0337 #endif
0338 }
0339
0340 template <class BidiIterator, class Allocator, class traits>
0341 bool perl_matcher<BidiIterator, Allocator, traits>::match_prefix()
0342 {
0343    m_has_partial_match = false;
0344    m_has_found_match = false;
0345    pstate = re.get_first_state();
0346    m_presult->set_first(position);
0347    restart = position;
0348    match_all_states();
0349    if(!m_has_found_match && m_has_partial_match && (m_match_flags & match_partial))
0350    {
0351       m_has_found_match = true;
0352       m_presult->set_second(last, 0, false);
0353       position = last;
0354       if((m_match_flags & match_posix) == match_posix)
0355       {
0356          m_result.maybe_assign(*m_presult);
0357       }
0358    }
0359 #ifdef BOOST_REGEX_MATCH_EXTRA
0360    if(m_has_found_match && (match_extra & m_match_flags))
0361    {
0362       //
0363       // we have a match, reverse the capture information:
0364       //
0365       for(unsigned i = 0; i < m_presult->size(); ++i)
0366       {
0367          typename sub_match<BidiIterator>::capture_sequence_type & seq = ((*m_presult)[i]).get_captures();
0368          std::reverse(seq.begin(), seq.end());
0369       }
0370    }
0371 #endif
0372    if(!m_has_found_match)
0373       position = restart; // reset search postion
0374 #ifdef BOOST_REGEX_RECURSIVE
0375    m_can_backtrack = true; // reset for further searches
0376 #endif
0377    return m_has_found_match;
0378 }
0379
0380 template <class BidiIterator, class Allocator, class traits>
0381 bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
0382 {
0383    unsigned int len = static_cast<const re_literal*>(pstate)->length;
0384    const char_type* what = reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
0385    //
0386    // compare string with what we stored in
0387    // our records:
0388    for(unsigned int i = 0; i < len; ++i, ++position)
0389    {
0390       if((position == last) || (traits_inst.translate(*position, icase) != what[i]))
0391          return false;
0392    }
0393    pstate = pstate->next.p;
0394    return true;
0395 }
0396
0397 template <class BidiIterator, class Allocator, class traits>
0398 bool perl_matcher<BidiIterator, Allocator, traits>::match_start_line()
0399 {
0400    if(position == backstop)
0401    {
0402       if((m_match_flags & match_prev_avail) == 0)
0403       {
0404          if((m_match_flags & match_not_bol) == 0)
0405          {
0406             pstate = pstate->next.p;
0407             return true;
0408          }
0409          return false;
0410       }
0411    }
0412    else if(m_match_flags & match_single_line)
0413       return false;
0414
0415    // check the previous value character:
0416    BidiIterator t(position);
0417    --t;
0418    if(position != last)
0419    {
0420       if(is_separator(*t) && !((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n'))) )
0421       {
0422          pstate = pstate->next.p;
0423          return true;
0424       }
0425    }
0426    else if(is_separator(*t))
0427    {
0428       pstate = pstate->next.p;
0429       return true;
0430    }
0431    return false;
0432 }
0433
0434 template <class BidiIterator, class Allocator, class traits>
0435 bool perl_matcher<BidiIterator, Allocator, traits>::match_end_line()
0436 {
0437    if(position != last)
0438    {
0439       if(m_match_flags & match_single_line)
0440          return false;
0441       // we're not yet at the end so *first is always valid:
0442       if(is_separator(*position))
0443       {
0444          if((position != backstop) || (m_match_flags & match_prev_avail))
0445          {
0446             // check that we're not in the middle of \r\n sequence
0447             BidiIterator t(position);
0448             --t;
0449             if((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n')))
0450             {
0451                return false;
0452             }
0453          }
0454          pstate = pstate->next.p;
0455          return true;
0456       }
0457    }
0458    else if((m_match_flags & match_not_eol) == 0)
0459    {
0460       pstate = pstate->next.p;
0461       return true;
0462    }
0463    return false;
0464 }
0465
0466 template <class BidiIterator, class Allocator, class traits>
0467 bool perl_matcher<BidiIterator, Allocator, traits>::match_wild()
0468 {
0469    if(position == last)
0470       return false;
0471    if(is_separator(*position) && ((match_any_mask & static_cast<const re_dot*>(pstate)->mask) == 0))
0472       return false;
0473    if((*position == char_type(0)) && (m_match_flags & match_not_dot_null))
0474       return false;
0475    pstate = pstate->next.p;
0476    ++position;
0477    return true;
0478 }
0479
0480 template <class BidiIterator, class Allocator, class traits>
0481 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
0482 {
0483    bool b; // indcates whether next character is a word character
0484    if(position != last)
0485    {
0486       // prev and this character must be opposites:
0487       b = traits_inst.isctype(*position, m_word_mask);
0488    }
0489    else
0490    {
0491       if (m_match_flags & match_not_eow)
0492          return false;
0493       b = false;
0494    }
0495    if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
0496    {
0497       if(m_match_flags & match_not_bow)
0498          return false;
0499       else
0500          b ^= false;
0501    }
0502    else
0503    {
0504       --position;
0505       b ^= traits_inst.isctype(*position, m_word_mask);
0506       ++position;
0507    }
0508    if(b)
0509    {
0510       pstate = pstate->next.p;
0511       return true;
0512    }
0513    return false; // no match if we get to here...
0514 }
0515
0516 template <class BidiIterator, class Allocator, class traits>
0517 bool perl_matcher<BidiIterator, Allocator, traits>::match_within_word()
0518 {
0519    if(position == last)
0520       return false;
0521    // both prev and this character must be m_word_mask:
0522    bool prev = traits_inst.isctype(*position, m_word_mask);
0523    {
0524       bool b;
0525       if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
0526          return false;
0527       else
0528       {
0529          --position;
0530          b = traits_inst.isctype(*position, m_word_mask);
0531          ++position;
0532       }
0533       if(b == prev)
0534       {
0535          pstate = pstate->next.p;
0536          return true;
0537       }
0538    }
0539    return false;
0540 }
0541
0542 template <class BidiIterator, class Allocator, class traits>
0543 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_start()
0544 {
0545    if(position == last)
0546       return false; // can't be starting a word if we're already at the end of input
0547    if(!traits_inst.isctype(*position, m_word_mask))
0548       return false; // next character isn't a word character
0549    if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
0550    {
0551       if(m_match_flags & match_not_bow)
0552          return false; // no previous input
0553    }
0554    else
0555    {
0556       // otherwise inside buffer:
0557       BidiIterator t(position);
0558       --t;
0559       if(traits_inst.isctype(*t, m_word_mask))
0560          return false; // previous character not non-word
0561    }
0562    // OK we have a match:
0563    pstate = pstate->next.p;
0564    return true;
0565 }
0566
0567 template <class BidiIterator, class Allocator, class traits>
0568 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_end()
0569 {
0570    if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
0571       return false;  // start of buffer can't be end of word
0572    BidiIterator t(position);
0573    --t;
0574    if(traits_inst.isctype(*t, m_word_mask) == false)
0575       return false;  // previous character wasn't a word character
0576
0577    if(position == last)
0578    {
0579       if(m_match_flags & match_not_eow)
0580          return false; // end of buffer but not end of word
0581    }
0582    else
0583    {
0584       // otherwise inside buffer:
0585       if(traits_inst.isctype(*position, m_word_mask))
0586          return false; // next character is a word character
0587    }
0588    pstate = pstate->next.p;
0589    return true;      // if we fall through to here then we've succeeded
0590 }
0591
0592 template <class BidiIterator, class Allocator, class traits>
0593 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start()
0594 {
0595    if((position != backstop) || (m_match_flags & match_not_bob))
0596       return false;
0597    // OK match:
0598    pstate = pstate->next.p;
0599    return true;
0600 }
0601
0602 template <class BidiIterator, class Allocator, class traits>
0603 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end()
0604 {
0605    if((position != last) || (m_match_flags & match_not_eob))
0606       return false;
0607    // OK match:
0608    pstate = pstate->next.p;
0609    return true;
0610 }
0611
0612 template <class BidiIterator, class Allocator, class traits>
0613 bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
0614 {
0615    //
0616    // Compare with what we previously matched.
0617    // Note that this succeeds if the backref did not partisipate
0618    // in the match, this is in line with ECMAScript, but not Perl
0619    // or PCRE.
0620    //
0621    int index = static_cast<const re_brace*>(pstate)->index;
0622    if(index >= hash_value_mask)
0623    {
0624       named_subexpressions::range_type r = re.get_data().equal_range(index);
0625       BOOST_REGEX_ASSERT(r.first != r.second);
0626       do
0627       {
0628          index = r.first->index;
0629          ++r.first;
0630       }while((r.first != r.second) && ((*m_presult)[index].matched != true));
0631    }
0632
0633    if((m_match_flags & match_perl) && !(*m_presult)[index].matched)
0634       return false;
0635
0636    BidiIterator i = (*m_presult)[index].first;
0637    BidiIterator j = (*m_presult)[index].second;
0638    while(i != j)
0639    {
0640       if((position == last) || (traits_inst.translate(*position, icase) != traits_inst.translate(*i, icase)))
0641          return false;
0642       ++i;
0643       ++position;
0644    }
0645    pstate = pstate->next.p;
0646    return true;
0647 }
0648
0649 template <class BidiIterator, class Allocator, class traits>
0650 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set()
0651 {
0652    typedef typename traits::char_class_type char_class_type;
0653    // let the traits class do the work:
0654    if(position == last)
0655       return false;
0656    BidiIterator t = re_is_set_member(position, last, static_cast<const re_set_long<char_class_type>*>(pstate), re.get_data(), icase);
0657    if(t != position)
0658    {
0659       pstate = pstate->next.p;
0660       position = t;
0661       return true;
0662    }
0663    return false;
0664 }
0665
0666 template <class BidiIterator, class Allocator, class traits>
0667 bool perl_matcher<BidiIterator, Allocator, traits>::match_set()
0668 {
0669    if(position == last)
0670       return false;
0671    if(static_cast<const re_set*>(pstate)->_map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0672    {
0673       pstate = pstate->next.p;
0674       ++position;
0675       return true;
0676    }
0677    return false;
0678 }
0679
0680 template <class BidiIterator, class Allocator, class traits>
0681 bool perl_matcher<BidiIterator, Allocator, traits>::match_jump()
0682 {
0683    pstate = static_cast<const re_jump*>(pstate)->alt.p;
0684    return true;
0685 }
0686
0687 template <class BidiIterator, class Allocator, class traits>
0688 bool perl_matcher<BidiIterator, Allocator, traits>::match_combining()
0689 {
0690    if(position == last)
0691       return false;
0692    if(is_combining(traits_inst.translate(*position, icase)))
0693       return false;
0694    ++position;
0695    while((position != last) && is_combining(traits_inst.translate(*position, icase)))
0696       ++position;
0697    pstate = pstate->next.p;
0698    return true;
0699 }
0700
0701 template <class BidiIterator, class Allocator, class traits>
0702 bool perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end()
0703 {
0704    if(m_match_flags & match_not_eob)
0705       return false;
0706    BidiIterator p(position);
0707    while((p != last) && is_separator(traits_inst.translate(*p, icase)))++p;
0708    if(p != last)
0709       return false;
0710    pstate = pstate->next.p;
0711    return true;
0712 }
0713
0714 template <class BidiIterator, class Allocator, class traits>
0715 bool perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue()
0716 {
0717    if(position == search_base)
0718    {
0719       pstate = pstate->next.p;
0720       return true;
0721    }
0722    return false;
0723 }
0724
0725 template <class BidiIterator, class Allocator, class traits>
0726 bool perl_matcher<BidiIterator, Allocator, traits>::match_backstep()
0727 {
0728 #ifdef BOOST_MSVC
0729 #pragma warning(push)
0730 #pragma warning(disable:4127)
0731 #endif
0732    if( ::boost::is_random_access_iterator<BidiIterator>::value)
0733    {
0734       std::ptrdiff_t maxlen = ::boost::BOOST_REGEX_DETAIL_NS::distance(backstop, position);
0735       if(maxlen < static_cast<const re_brace*>(pstate)->index)
0736          return false;
0737       std::advance(position, -static_cast<const re_brace*>(pstate)->index);
0738    }
0739    else
0740    {
0741       int c = static_cast<const re_brace*>(pstate)->index;
0742       while(c--)
0743       {
0744          if(position == backstop)
0745             return false;
0746          --position;
0747       }
0748    }
0749    pstate = pstate->next.p;
0750    return true;
0751 #ifdef BOOST_MSVC
0752 #pragma warning(pop)
0753 #endif
0754 }
0755
0756 template <class BidiIterator, class Allocator, class traits>
0757 inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
0758 {
0759    // return true if marked sub-expression N has been matched:
0760    int index = static_cast<const re_brace*>(pstate)->index;
0761    bool result = false;
0762    if(index == 9999)
0763    {
0764       // Magic value for a (DEFINE) block:
0765       return false;
0766    }
0767    else if(index > 0)
0768    {
0769       // Have we matched subexpression "index"?
0770       // Check if index is a hash value:
0771       if(index >= hash_value_mask)
0772       {
0773          named_subexpressions::range_type r = re.get_data().equal_range(index);
0774          while(r.first != r.second)
0775          {
0776             if((*m_presult)[r.first->index].matched)
0777             {
0778                result = true;
0779                break;
0780             }
0781             ++r.first;
0782          }
0783       }
0784       else
0785       {
0786          result = (*m_presult)[index].matched;
0787       }
0788       pstate = pstate->next.p;
0789    }
0790    else
0791    {
0792       // Have we recursed into subexpression "index"?
0793       // If index == 0 then check for any recursion at all, otherwise for recursion to -index-1.
0794       int idx = -(index+1);
0795       if(idx >= hash_value_mask)
0796       {
0797          named_subexpressions::range_type r = re.get_data().equal_range(idx);
0798          int stack_index = recursion_stack.empty() ? -1 : recursion_stack.back().idx;
0799          while(r.first != r.second)
0800          {
0801             result |= (stack_index == r.first->index);
0802             if(result)break;
0803             ++r.first;
0804          }
0805       }
0806       else
0807       {
0808          result = !recursion_stack.empty() && ((recursion_stack.back().idx == idx) || (index == 0));
0809       }
0810       pstate = pstate->next.p;
0811    }
0812    return result;
0813 }
0814
0815 template <class BidiIterator, class Allocator, class traits>
0816 bool perl_matcher<BidiIterator, Allocator, traits>::match_fail()
0817 {
0818    // Just force a backtrack:
0819    return false;
0820 }
0821
0822 template <class BidiIterator, class Allocator, class traits>
0823 bool perl_matcher<BidiIterator, Allocator, traits>::match_accept()
0824 {
0825    if(!recursion_stack.empty())
0826    {
0827       return skip_until_paren(recursion_stack.back().idx);
0828    }
0829    else
0830    {
0831       return skip_until_paren(INT_MAX);
0832    }
0833 }
0834
0835 template <class BidiIterator, class Allocator, class traits>
0836 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_any()
0837 {
0838 #ifdef BOOST_MSVC
0839 #pragma warning(push)
0840 #pragma warning(disable:4127)
0841 #endif
0842    const unsigned char* _map = re.get_map();
0843    while(true)
0844    {
0845       // skip everything we can't match:
0846       while((position != last) && !can_start(*position, _map, (unsigned char)mask_any) )
0847          ++position;
0848       if(position == last)
0849       {
0850          // run out of characters, try a null match if possible:
0851          if(re.can_be_null())
0852             return match_prefix();
0853          break;
0854       }
0855       // now try and obtain a match:
0856       if(match_prefix())
0857          return true;
0858       if(position == last)
0859          return false;
0860       ++position;
0861    }
0862    return false;
0863 #ifdef BOOST_MSVC
0864 #pragma warning(pop)
0865 #endif
0866 }
0867
0868 template <class BidiIterator, class Allocator, class traits>
0869 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_word()
0870 {
0871 #ifdef BOOST_MSVC
0872 #pragma warning(push)
0873 #pragma warning(disable:4127)
0874 #endif
0875    // do search optimised for word starts:
0876    const unsigned char* _map = re.get_map();
0877    if((m_match_flags & match_prev_avail) || (position != base))
0878       --position;
0879    else if(match_prefix())
0880       return true;
0881    do
0882    {
0883       while((position != last) && traits_inst.isctype(*position, m_word_mask))
0884          ++position;
0885       while((position != last) && !traits_inst.isctype(*position, m_word_mask))
0886          ++position;
0887       if(position == last)
0888          break;
0889
0890       if(can_start(*position, _map, (unsigned char)mask_any) )
0891       {
0892          if(match_prefix())
0893             return true;
0894       }
0895       if(position == last)
0896          break;
0897    } while(true);
0898    return false;
0899 #ifdef BOOST_MSVC
0900 #pragma warning(pop)
0901 #endif
0902 }
0903
0904 template <class BidiIterator, class Allocator, class traits>
0905 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_line()
0906 {
0907    // do search optimised for line starts:
0908    const unsigned char* _map = re.get_map();
0909    if(match_prefix())
0910       return true;
0911    while(position != last)
0912    {
0913       while((position != last) && !is_separator(*position))
0914          ++position;
0915       if(position == last)
0916          return false;
0917       ++position;
0918       if(position == last)
0919       {
0920          if(re.can_be_null() && match_prefix())
0921             return true;
0922          return false;
0923       }
0924
0925       if( can_start(*position, _map, (unsigned char)mask_any) )
0926       {
0927          if(match_prefix())
0928             return true;
0929       }
0930       if(position == last)
0931          return false;
0932       //++position;
0933    }
0934    return false;
0935 }
0936
0937 template <class BidiIterator, class Allocator, class traits>
0938 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf()
0939 {
0940    if((position == base) && ((m_match_flags & match_not_bob) == 0))
0941       return match_prefix();
0942    return false;
0943 }
0944
0945 template <class BidiIterator, class Allocator, class traits>
0946 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit()
0947 {
0948 #if 0
0949    if(position == last)
0950       return false; // can't possibly match if we're at the end already
0951
0952    unsigned type = (m_match_flags & match_continuous) ?
0953       static_cast<unsigned int>(regbase::restart_continue)
0954          : static_cast<unsigned int>(re.get_restart_type());
0955
0956    const kmp_info<char_type>* info = access::get_kmp(re);
0957    int len = info->len;
0958    const char_type* x = info->pstr;
0959    int j = 0;
0960    while (position != last)
0961    {
0962       while((j > -1) && (x[j] != traits_inst.translate(*position, icase)))
0963          j = info->kmp_next[j];
0964       ++position;
0965       ++j;
0966       if(j >= len)
0967       {
0968          if(type == regbase::restart_fixed_lit)
0969          {
0970             std::advance(position, -j);
0971             restart = position;
0972             std::advance(restart, len);
0973             m_result.set_first(position);
0974             m_result.set_second(restart);
0975             position = restart;
0976             return true;
0977          }
0978          else
0979          {
0980             restart = position;
0981             std::advance(position, -j);
0982             if(match_prefix())
0983                return true;
0984             else
0985             {
0986                for(int k = 0; (restart != position) && (k < j); ++k, --restart)
0987                      {} // dwa 10/20/2000 - warning suppression for MWCW
0988                if(restart != last)
0989                   ++restart;
0990                position = restart;
0991                j = 0;  //we could do better than this...
0992             }
0993          }
0994       }
0995    }
0996    if((m_match_flags & match_partial) && (position == last) && j)
0997    {
0998       // we need to check for a partial match:
0999       restart = position;
1000       std::advance(position, -j);
1001       return match_prefix();
1002    }
1003 #endif
1004    return false;
1005 }
1006
1007 } // namespace BOOST_REGEX_DETAIL_NS
1008
1009 } // namespace boost
1010
1011 #ifdef BOOST_MSVC
1012 #  pragma warning(pop)
1013 #endif
1014
1015 #ifdef BOOST_BORLANDC
1016 #  pragma option pop
1017 #endif
1018 #ifdef BOOST_MSVC
1019 #pragma warning(push)
1020 #pragma warning(disable: 4103)
1021 #endif
1022 #ifdef BOOST_HAS_ABI_HEADERS
1023 #  include BOOST_ABI_SUFFIX
1024 #endif
1025 #ifdef BOOST_MSVC
1026 #pragma warning(pop)
1027 #endif
1028
1029 #endif
1030