regex/v4/perl_matcher_recursive.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   *                specific to the recursive implementation.
0018   */
0019
0020 #ifndef BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
0021 #define BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
0022
0023 #ifdef BOOST_MSVC
0024 #pragma warning(push)
0025 #pragma warning(disable: 4103)
0026 #endif
0027 #ifdef BOOST_HAS_ABI_HEADERS
0028 #  include BOOST_ABI_PREFIX
0029 #endif
0030 #ifdef BOOST_MSVC
0031 #pragma warning(pop)
0032 #endif
0033
0034 #ifdef BOOST_MSVC
0035 #pragma warning(push)
0036 #pragma warning(disable: 4800)
0037 #endif
0038
0039 namespace boost{
0040 namespace BOOST_REGEX_DETAIL_NS{
0041
0042 template <class BidiIterator>
0043 class backup_subex
0044 {
0045    int index;
0046    sub_match<BidiIterator> sub;
0047 public:
0048    template <class A>
0049    backup_subex(const match_results<BidiIterator, A>& w, int i)
0050       : index(i), sub(w[i], false) {}
0051    template <class A>
0052    void restore(match_results<BidiIterator, A>& w)
0053    {
0054       w.set_first(sub.first, index, index == 0);
0055       w.set_second(sub.second, index, sub.matched, index == 0);
0056    }
0057    const sub_match<BidiIterator>& get() { return sub; }
0058 };
0059
0060 template <class BidiIterator, class Allocator, class traits>
0061 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
0062 {
0063    static matcher_proc_type const s_match_vtable[34] =
0064    {
0065       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
0066       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
0067       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
0068       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
0069       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
0070       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
0071       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
0072       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
0073       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
0074       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
0075       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
0076       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
0077       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
0078       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
0079       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
0080       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
0081       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
0082       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
0083       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
0084       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
0085       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
0086       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
0087       // Although this next line *should* be evaluated at compile time, in practice
0088       // some compilers (VC++) emit run-time initialisation which breaks thread
0089       // safety, so use a dispatch function instead:
0090       //(::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),
0091       &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
0092       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
0093       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
0094       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
0095       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
0096       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
0097       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
0098       &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
0099       &perl_matcher<BidiIterator, Allocator, traits>::match_fail,
0100       &perl_matcher<BidiIterator, Allocator, traits>::match_accept,
0101       &perl_matcher<BidiIterator, Allocator, traits>::match_commit,
0102       &perl_matcher<BidiIterator, Allocator, traits>::match_then,
0103    };
0104
0105    if(state_count > max_state_count)
0106       raise_error(traits_inst, regex_constants::error_complexity);
0107    while(pstate)
0108    {
0109       matcher_proc_type proc = s_match_vtable[pstate->type];
0110       ++state_count;
0111       if(!(this->*proc)())
0112       {
0113          if((m_match_flags & match_partial) && (position == last) && (position != search_base))
0114             m_has_partial_match = true;
0115          return 0;
0116       }
0117    }
0118    return true;
0119 }
0120
0121 template <class BidiIterator, class Allocator, class traits>
0122 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
0123 {
0124    int index = static_cast<const re_brace*>(pstate)->index;
0125    icase = static_cast<const re_brace*>(pstate)->icase;
0126    bool r = true;
0127    switch(index)
0128    {
0129    case 0:
0130       pstate = pstate->next.p;
0131       break;
0132    case -1:
0133    case -2:
0134       {
0135          // forward lookahead assert:
0136          BidiIterator old_position(position);
0137          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
0138          pstate = pstate->next.p->next.p;
0139          r = match_all_states();
0140          pstate = next_pstate;
0141          position = old_position;
0142          if((r && (index != -1)) || (!r && (index != -2)))
0143             r = false;
0144          else
0145             r = true;
0146          if(r && m_have_accept)
0147             r = skip_until_paren(INT_MAX);
0148          break;
0149       }
0150    case -3:
0151       {
0152          // independent sub-expression:
0153          bool old_independent = m_independent;
0154          m_independent = true;
0155          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
0156          pstate = pstate->next.p->next.p;
0157          bool can_backtrack = m_can_backtrack;
0158          r = match_all_states();
0159          if(r)
0160             m_can_backtrack = can_backtrack;
0161          pstate = next_pstate;
0162          m_independent = old_independent;
0163 #ifdef BOOST_REGEX_MATCH_EXTRA
0164          if(r && (m_match_flags & match_extra))
0165          {
0166             //
0167             // our captures have been stored in *m_presult
0168             // we need to unpack them, and insert them
0169             // back in the right order when we unwind the stack:
0170             //
0171             unsigned i;
0172             match_results<BidiIterator, Allocator> tm(*m_presult);
0173             for(i = 0; i < tm.size(); ++i)
0174                (*m_presult)[i].get_captures().clear();
0175             // match everything else:
0176             r = match_all_states();
0177             // now place the stored captures back:
0178             for(i = 0; i < tm.size(); ++i)
0179             {
0180                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
0181                seq& s1 = (*m_presult)[i].get_captures();
0182                const seq& s2 = tm[i].captures();
0183                s1.insert(
0184                   s1.end(),
0185                   s2.begin(),
0186                   s2.end());
0187             }
0188          }
0189 #endif
0190          if(r && m_have_accept)
0191             r = skip_until_paren(INT_MAX);
0192          break;
0193       }
0194    case -4:
0195       {
0196       // conditional expression:
0197       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
0198       BOOST_REGEX_ASSERT(alt->type == syntax_element_alt);
0199       pstate = alt->next.p;
0200       if(pstate->type == syntax_element_assert_backref)
0201       {
0202          if(!match_assert_backref())
0203             pstate = alt->alt.p;
0204          break;
0205       }
0206       else
0207       {
0208          // zero width assertion, have to match this recursively:
0209          BOOST_REGEX_ASSERT(pstate->type == syntax_element_startmark);
0210          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
0211          BidiIterator saved_position = position;
0212          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
0213          pstate = pstate->next.p->next.p;
0214          bool res = match_all_states();
0215          position = saved_position;
0216          if(negated)
0217             res = !res;
0218          if(res)
0219             pstate = next_pstate;
0220          else
0221             pstate = alt->alt.p;
0222          break;
0223       }
0224       }
0225    case -5:
0226       {
0227          // Reset start of $0, since we have a \K escape
0228          backup_subex<BidiIterator> sub(*m_presult, 0);
0229          m_presult->set_first(position, 0, true);
0230          pstate = pstate->next.p;
0231          r = match_all_states();
0232          if(r == false)
0233             sub.restore(*m_presult);
0234          break;
0235       }
0236    default:
0237    {
0238       BOOST_REGEX_ASSERT(index > 0);
0239       if((m_match_flags & match_nosubs) == 0)
0240       {
0241          backup_subex<BidiIterator> sub(*m_presult, index);
0242          m_presult->set_first(position, index);
0243          pstate = pstate->next.p;
0244          r = match_all_states();
0245          if(r == false)
0246             sub.restore(*m_presult);
0247 #ifdef BOOST_REGEX_MATCH_EXTRA
0248          //
0249          // we have a match, push the capture information onto the stack:
0250          //
0251          else if(sub.get().matched && (match_extra & m_match_flags))
0252             ((*m_presult)[index]).get_captures().push_back(sub.get());
0253 #endif
0254       }
0255       else
0256       {
0257          pstate = pstate->next.p;
0258       }
0259       break;
0260    }
0261    }
0262    return r;
0263 }
0264
0265 template <class BidiIterator, class Allocator, class traits>
0266 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
0267 {
0268    bool take_first, take_second;
0269    const re_alt* jmp = static_cast<const re_alt*>(pstate);
0270
0271    // find out which of these two alternatives we need to take:
0272    if(position == last)
0273    {
0274       take_first = jmp->can_be_null & mask_take;
0275       take_second = jmp->can_be_null & mask_skip;
0276    }
0277    else
0278    {
0279       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
0280       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
0281   }
0282
0283    if(take_first)
0284    {
0285       // we can take the first alternative,
0286       // see if we need to push next alternative:
0287       if(take_second)
0288       {
0289          BidiIterator oldposition(position);
0290          const re_syntax_base* old_pstate = jmp->alt.p;
0291          pstate = pstate->next.p;
0292          bool oldcase = icase;
0293          m_have_then = false;
0294          if(!match_all_states())
0295          {
0296             pstate = old_pstate;
0297             position = oldposition;
0298             icase = oldcase;
0299             if(m_have_then)
0300             {
0301                m_can_backtrack = true;
0302                m_have_then = false;
0303                return false;
0304             }
0305          }
0306          m_have_then = false;
0307          return m_can_backtrack;
0308       }
0309       pstate = pstate->next.p;
0310       return true;
0311    }
0312    if(take_second)
0313    {
0314       pstate = jmp->alt.p;
0315       return true;
0316    }
0317    return false;  // neither option is possible
0318 }
0319
0320 template <class BidiIterator, class Allocator, class traits>
0321 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
0322 {
0323 #ifdef BOOST_MSVC
0324 #pragma warning(push)
0325 #pragma warning(disable:4127 4244)
0326 #endif
0327    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0328    //
0329    // Always copy the repeat count, so that the state is restored
0330    // when we exit this scope:
0331    //
0332    repeater_count<BidiIterator> r(rep->state_id, &next_count, position, this->recursion_stack.size() ? this->recursion_stack.back().idx : INT_MIN + 3);
0333    //
0334    // If we've had at least one repeat already, and the last one
0335    // matched the NULL string then set the repeat count to
0336    // maximum:
0337    //
0338    next_count->check_null_repeat(position, rep->max);
0339
0340    // find out which of these two alternatives we need to take:
0341    bool take_first, take_second;
0342    if(position == last)
0343    {
0344       take_first = rep->can_be_null & mask_take;
0345       take_second = rep->can_be_null & mask_skip;
0346    }
0347    else
0348    {
0349       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
0350       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
0351    }
0352
0353    if(next_count->get_count() < rep->min)
0354    {
0355       // we must take the repeat:
0356       if(take_first)
0357       {
0358          // increase the counter:
0359          ++(*next_count);
0360          pstate = rep->next.p;
0361          return match_all_states();
0362       }
0363       return false;
0364    }
0365    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0366    if(greedy)
0367    {
0368       // try and take the repeat if we can:
0369       if((next_count->get_count() < rep->max) && take_first)
0370       {
0371          // store position in case we fail:
0372          BidiIterator pos = position;
0373          // increase the counter:
0374          ++(*next_count);
0375          pstate = rep->next.p;
0376          if(match_all_states())
0377             return true;
0378          if(!m_can_backtrack)
0379             return false;
0380          // failed repeat, reset posistion and fall through for alternative:
0381          position = pos;
0382       }
0383       if(take_second)
0384       {
0385          pstate = rep->alt.p;
0386          return true;
0387       }
0388       return false; // can't take anything, fail...
0389    }
0390    else // non-greedy
0391    {
0392       // try and skip the repeat if we can:
0393       if(take_second)
0394       {
0395          // store position in case we fail:
0396          BidiIterator pos = position;
0397          pstate = rep->alt.p;
0398          if(match_all_states())
0399             return true;
0400          if(!m_can_backtrack)
0401             return false;
0402          // failed alternative, reset posistion and fall through for repeat:
0403          position = pos;
0404       }
0405       if((next_count->get_count() < rep->max) && take_first)
0406       {
0407          // increase the counter:
0408          ++(*next_count);
0409          pstate = rep->next.p;
0410          return match_all_states();
0411       }
0412    }
0413    return false;
0414 #ifdef BOOST_MSVC
0415 #pragma warning(pop)
0416 #endif
0417 }
0418
0419 template <class BidiIterator, class Allocator, class traits>
0420 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
0421 {
0422 #ifdef BOOST_MSVC
0423 #pragma warning(push)
0424 #pragma warning(disable:4127)
0425 #endif
0426    std::size_t count = 0;
0427    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0428    re_syntax_base* psingle = rep->next.p;
0429    // match compulsary repeats first:
0430    while(count < rep->min)
0431    {
0432       pstate = psingle;
0433       if(!match_wild())
0434          return false;
0435       ++count;
0436    }
0437    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0438    if(greedy)
0439    {
0440       // normal repeat:
0441       while(count < rep->max)
0442       {
0443          pstate = psingle;
0444          if(!match_wild())
0445             break;
0446          ++count;
0447       }
0448       if((rep->leading) && (count < rep->max))
0449          restart = position;
0450       pstate = rep;
0451       return backtrack_till_match(count - rep->min);
0452    }
0453    else
0454    {
0455       // non-greedy, keep trying till we get a match:
0456       BidiIterator save_pos;
0457       do
0458       {
0459          if((rep->leading) && (rep->max == UINT_MAX))
0460             restart = position;
0461          pstate = rep->alt.p;
0462          save_pos = position;
0463          ++state_count;
0464          if(match_all_states())
0465             return true;
0466          if((count >= rep->max) || !m_can_backtrack)
0467             return false;
0468          ++count;
0469          pstate = psingle;
0470          position = save_pos;
0471          if(!match_wild())
0472             return false;
0473       }while(true);
0474    }
0475 #ifdef BOOST_MSVC
0476 #pragma warning(pop)
0477 #endif
0478 }
0479
0480 template <class BidiIterator, class Allocator, class traits>
0481 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
0482 {
0483 #ifdef BOOST_MSVC
0484 #pragma warning(push)
0485 #pragma warning(disable:4127)
0486 #endif
0487    if(m_match_flags & match_not_dot_null)
0488       return match_dot_repeat_slow();
0489    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
0490       return match_dot_repeat_slow();
0491    //
0492    // start by working out how much we can skip:
0493    //
0494    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0495 #ifdef BOOST_MSVC
0496 #pragma warning(push)
0497 #pragma warning(disable:4267)
0498 #endif
0499    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0500    std::size_t count = (std::min)(static_cast<std::size_t>(::boost::BOOST_REGEX_DETAIL_NS::distance(position, last)), greedy ? rep->max : rep->min);
0501    if(rep->min > count)
0502    {
0503       position = last;
0504       return false;  // not enough text left to match
0505    }
0506    std::advance(position, count);
0507 #ifdef BOOST_MSVC
0508 #pragma warning(pop)
0509 #endif
0510    if((rep->leading) && (count < rep->max) && greedy)
0511       restart = position;
0512    if(greedy)
0513       return backtrack_till_match(count - rep->min);
0514
0515    // non-greedy, keep trying till we get a match:
0516    BidiIterator save_pos;
0517    do
0518    {
0519       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
0520       {
0521          ++position;
0522          ++count;
0523       }
0524       if((rep->leading) && (rep->max == UINT_MAX))
0525          restart = position;
0526       pstate = rep->alt.p;
0527       save_pos = position;
0528       ++state_count;
0529       if(match_all_states())
0530          return true;
0531       if((count >= rep->max) || !m_can_backtrack)
0532          return false;
0533       if(save_pos == last)
0534          return false;
0535       position = ++save_pos;
0536       ++count;
0537    }while(true);
0538 #ifdef BOOST_MSVC
0539 #pragma warning(pop)
0540 #endif
0541 }
0542
0543 template <class BidiIterator, class Allocator, class traits>
0544 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
0545 {
0546 #ifdef BOOST_MSVC
0547 #pragma warning(push)
0548 #pragma warning(disable:4127)
0549 #pragma warning(disable:4267)
0550 #endif
0551 #ifdef BOOST_BORLANDC
0552 #pragma option push -w-8008 -w-8066 -w-8004
0553 #endif
0554    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0555    BOOST_REGEX_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
0556    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
0557    //
0558    // start by working out how much we can skip:
0559    //
0560    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0561    std::size_t count, desired;
0562    if(::boost::is_random_access_iterator<BidiIterator>::value)
0563    {
0564       desired =
0565          (std::min)(
0566             (std::size_t)(greedy ? rep->max : rep->min),
0567             (std::size_t)::boost::BOOST_REGEX_DETAIL_NS::distance(position, last));
0568       count = desired;
0569       ++desired;
0570       if(icase)
0571       {
0572          while(--desired && (traits_inst.translate_nocase(*position) == what))
0573          {
0574             ++position;
0575          }
0576       }
0577       else
0578       {
0579          while(--desired && (traits_inst.translate(*position) == what))
0580          {
0581             ++position;
0582          }
0583       }
0584       count = count - desired;
0585    }
0586    else
0587    {
0588       count = 0;
0589       desired = greedy ? rep->max : rep->min;
0590       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
0591       {
0592          ++position;
0593          ++count;
0594       }
0595    }
0596    if((rep->leading) && (count < rep->max) && greedy)
0597       restart = position;
0598    if(count < rep->min)
0599       return false;
0600
0601    if(greedy)
0602       return backtrack_till_match(count - rep->min);
0603
0604    // non-greedy, keep trying till we get a match:
0605    BidiIterator save_pos;
0606    do
0607    {
0608       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
0609       {
0610          if((traits_inst.translate(*position, icase) == what))
0611          {
0612             ++position;
0613             ++count;
0614          }
0615          else
0616             return false;  // counldn't repeat even though it was the only option
0617       }
0618       if((rep->leading) && (rep->max == UINT_MAX))
0619          restart = position;
0620       pstate = rep->alt.p;
0621       save_pos = position;
0622       ++state_count;
0623       if(match_all_states())
0624          return true;
0625       if((count >= rep->max) || !m_can_backtrack)
0626          return false;
0627       position = save_pos;
0628       if(position == last)
0629          return false;
0630       if(traits_inst.translate(*position, icase) == what)
0631       {
0632          ++position;
0633          ++count;
0634       }
0635       else
0636       {
0637          return false;
0638       }
0639    }while(true);
0640 #ifdef BOOST_BORLANDC
0641 #pragma option pop
0642 #endif
0643 #ifdef BOOST_MSVC
0644 #pragma warning(pop)
0645 #endif
0646 }
0647
0648 template <class BidiIterator, class Allocator, class traits>
0649 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
0650 {
0651 #ifdef BOOST_MSVC
0652 #pragma warning(push)
0653 #pragma warning(disable:4127)
0654 #endif
0655 #ifdef BOOST_BORLANDC
0656 #pragma option push -w-8008 -w-8066 -w-8004
0657 #endif
0658    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0659    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
0660    std::size_t count = 0;
0661    //
0662    // start by working out how much we can skip:
0663    //
0664    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0665    std::size_t desired = greedy ? rep->max : rep->min;
0666    if(::boost::is_random_access_iterator<BidiIterator>::value)
0667    {
0668       BidiIterator end = position;
0669       // Move end forward by "desired", preferably without using distance or advance if we can
0670       // as these can be slow for some iterator types.
0671       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
0672       if(desired >= len)
0673          end = last;
0674       else
0675          std::advance(end, desired);
0676       BidiIterator origin(position);
0677       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0678       {
0679          ++position;
0680       }
0681       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
0682    }
0683    else
0684    {
0685       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0686       {
0687          ++position;
0688          ++count;
0689       }
0690    }
0691    if((rep->leading) && (count < rep->max) && greedy)
0692       restart = position;
0693    if(count < rep->min)
0694       return false;
0695
0696    if(greedy)
0697       return backtrack_till_match(count - rep->min);
0698
0699    // non-greedy, keep trying till we get a match:
0700    BidiIterator save_pos;
0701    do
0702    {
0703       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
0704       {
0705          if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0706          {
0707             ++position;
0708             ++count;
0709          }
0710          else
0711             return false;  // counldn't repeat even though it was the only option
0712       }
0713       if((rep->leading) && (rep->max == UINT_MAX))
0714          restart = position;
0715       pstate = rep->alt.p;
0716       save_pos = position;
0717       ++state_count;
0718       if(match_all_states())
0719          return true;
0720       if((count >= rep->max) || !m_can_backtrack)
0721          return false;
0722       position = save_pos;
0723       if(position == last)
0724          return false;
0725       if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0726       {
0727          ++position;
0728          ++count;
0729       }
0730       else
0731       {
0732          return false;
0733       }
0734    }while(true);
0735 #ifdef BOOST_BORLANDC
0736 #pragma option pop
0737 #endif
0738 #ifdef BOOST_MSVC
0739 #pragma warning(pop)
0740 #endif
0741 }
0742
0743 template <class BidiIterator, class Allocator, class traits>
0744 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
0745 {
0746 #ifdef BOOST_MSVC
0747 #pragma warning(push)
0748 #pragma warning(disable:4127)
0749 #endif
0750 #ifdef BOOST_BORLANDC
0751 #pragma option push -w-8008 -w-8066 -w-8004
0752 #endif
0753    typedef typename traits::char_class_type char_class_type;
0754    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0755    const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
0756    std::size_t count = 0;
0757    //
0758    // start by working out how much we can skip:
0759    //
0760    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0761    std::size_t desired = greedy ? rep->max : rep->min;
0762    if(::boost::is_random_access_iterator<BidiIterator>::value)
0763    {
0764       BidiIterator end = position;
0765       // Move end forward by "desired", preferably without using distance or advance if we can
0766       // as these can be slow for some iterator types.
0767       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
0768       if(desired >= len)
0769          end = last;
0770       else
0771          std::advance(end, desired);
0772       BidiIterator origin(position);
0773       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
0774       {
0775          ++position;
0776       }
0777       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
0778    }
0779    else
0780    {
0781       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
0782       {
0783          ++position;
0784          ++count;
0785       }
0786    }
0787    if((rep->leading) && (count < rep->max) && greedy)
0788       restart = position;
0789    if(count < rep->min)
0790       return false;
0791
0792    if(greedy)
0793       return backtrack_till_match(count - rep->min);
0794
0795    // non-greedy, keep trying till we get a match:
0796    BidiIterator save_pos;
0797    do
0798    {
0799       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
0800       {
0801          if(position != re_is_set_member(position, last, set, re.get_data(), icase))
0802          {
0803             ++position;
0804             ++count;
0805          }
0806          else
0807             return false;  // counldn't repeat even though it was the only option
0808       }
0809       if((rep->leading) && (rep->max == UINT_MAX))
0810          restart = position;
0811       pstate = rep->alt.p;
0812       save_pos = position;
0813       ++state_count;
0814       if(match_all_states())
0815          return true;
0816       if((count >= rep->max) || !m_can_backtrack)
0817          return false;
0818       position = save_pos;
0819       if(position == last)
0820          return false;
0821       if(position != re_is_set_member(position, last, set, re.get_data(), icase))
0822       {
0823          ++position;
0824          ++count;
0825       }
0826       else
0827       {
0828          return false;
0829       }
0830    }while(true);
0831 #ifdef BOOST_BORLANDC
0832 #pragma option pop
0833 #endif
0834 #ifdef BOOST_MSVC
0835 #pragma warning(pop)
0836 #endif
0837 }
0838
0839 template <class BidiIterator, class Allocator, class traits>
0840 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
0841 {
0842 #ifdef BOOST_MSVC
0843 #pragma warning(push)
0844 #pragma warning(disable:4127)
0845 #endif
0846    if(!m_can_backtrack)
0847       return false;
0848    if((m_match_flags & match_partial) && (position == last))
0849       m_has_partial_match = true;
0850
0851    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0852    BidiIterator backtrack = position;
0853    if(position == last)
0854    {
0855       if(rep->can_be_null & mask_skip)
0856       {
0857          pstate = rep->alt.p;
0858          if(match_all_states())
0859             return true;
0860       }
0861       if(count)
0862       {
0863          position = --backtrack;
0864          --count;
0865       }
0866       else
0867          return false;
0868    }
0869    do
0870    {
0871       while(count && !can_start(*position, rep->_map, mask_skip))
0872       {
0873          --position;
0874          --count;
0875          ++state_count;
0876       }
0877       pstate = rep->alt.p;
0878       backtrack = position;
0879       if(match_all_states())
0880          return true;
0881       if(count == 0)
0882          return false;
0883       position = --backtrack;
0884       ++state_count;
0885       --count;
0886    }while(true);
0887 #ifdef BOOST_MSVC
0888 #pragma warning(pop)
0889 #endif
0890 }
0891
0892 template <class BidiIterator, class Allocator, class traits>
0893 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
0894 {
0895    BOOST_REGEX_ASSERT(pstate->type == syntax_element_recurse);
0896    //
0897    // Set new call stack:
0898    //
0899    if(recursion_stack.capacity() == 0)
0900    {
0901       recursion_stack.reserve(50);
0902    }
0903    //
0904    // See if we've seen this recursion before at this location, if we have then
0905    // we need to prevent infinite recursion:
0906    //
0907    for(typename std::vector<recursion_info<results_type> >::reverse_iterator i = recursion_stack.rbegin(); i != recursion_stack.rend(); ++i)
0908    {
0909       if(i->idx == static_cast<const re_brace*>(static_cast<const re_jump*>(pstate)->alt.p)->index)
0910       {
0911          if(i->location_of_start == position)
0912             return false;
0913          break;
0914       }
0915    }
0916    //
0917    // Now get on with it:
0918    //
0919    recursion_stack.push_back(recursion_info<results_type>());
0920    recursion_stack.back().preturn_address = pstate->next.p;
0921    recursion_stack.back().results = *m_presult;
0922    recursion_stack.back().repeater_stack = next_count;
0923    recursion_stack.back().location_of_start = position;
0924    pstate = static_cast<const re_jump*>(pstate)->alt.p;
0925    recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
0926
0927    repeater_count<BidiIterator>* saved = next_count;
0928    repeater_count<BidiIterator> r(&next_count); // resets all repeat counts since we're recursing and starting fresh on those
0929    next_count = &r;
0930    bool can_backtrack = m_can_backtrack;
0931    bool result = match_all_states();
0932    m_can_backtrack = can_backtrack;
0933    next_count = saved;
0934
0935    if(!result)
0936    {
0937       next_count = recursion_stack.back().repeater_stack;
0938       *m_presult = recursion_stack.back().results;
0939       recursion_stack.pop_back();
0940       return false;
0941    }
0942    return true;
0943 }
0944
0945 template <class BidiIterator, class Allocator, class traits>
0946 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
0947 {
0948    int index = static_cast<const re_brace*>(pstate)->index;
0949    icase = static_cast<const re_brace*>(pstate)->icase;
0950    if(index > 0)
0951    {
0952       if((m_match_flags & match_nosubs) == 0)
0953       {
0954          m_presult->set_second(position, index);
0955       }
0956       if(!recursion_stack.empty())
0957       {
0958          if(index == recursion_stack.back().idx)
0959          {
0960             recursion_info<results_type> saved = recursion_stack.back();
0961             recursion_stack.pop_back();
0962             pstate = saved.preturn_address;
0963             repeater_count<BidiIterator>* saved_count = next_count;
0964             next_count = saved.repeater_stack;
0965             *m_presult = saved.results;
0966             if(!match_all_states())
0967             {
0968                recursion_stack.push_back(saved);
0969                next_count = saved_count;
0970                return false;
0971             }
0972          }
0973       }
0974    }
0975    else if((index < 0) && (index != -4))
0976    {
0977       // matched forward lookahead:
0978       pstate = 0;
0979       return true;
0980    }
0981    pstate = pstate ? pstate->next.p : 0;
0982    return true;
0983 }
0984
0985 template <class BidiIterator, class Allocator, class traits>
0986 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
0987 {
0988    if(!recursion_stack.empty())
0989    {
0990       BOOST_REGEX_ASSERT(0 == recursion_stack.back().idx);
0991       const re_syntax_base* saved_state = pstate = recursion_stack.back().preturn_address;
0992       *m_presult = recursion_stack.back().results;
0993       recursion_stack.pop_back();
0994       if(!match_all_states())
0995       {
0996          recursion_stack.push_back(recursion_info<results_type>());
0997          recursion_stack.back().preturn_address = saved_state;
0998          recursion_stack.back().results = *m_presult;
0999          recursion_stack.back().location_of_start = position;
1000          return false;
1001       }
1002       return true;
1003    }
1004    if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
1005       return false;
1006    if((m_match_flags & match_all) && (position != last))
1007       return false;
1008    if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
1009       return false;
1010    m_presult->set_second(position);
1011    pstate = 0;
1012    m_has_found_match = true;
1013    if((m_match_flags & match_posix) == match_posix)
1014    {
1015       m_result.maybe_assign(*m_presult);
1016       if((m_match_flags & match_any) == 0)
1017          return false;
1018    }
1019 #ifdef BOOST_REGEX_MATCH_EXTRA
1020    if(match_extra & m_match_flags)
1021    {
1022       for(unsigned i = 0; i < m_presult->size(); ++i)
1023          if((*m_presult)[i].matched)
1024             ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
1025    }
1026 #endif
1027    return true;
1028 }
1029
1030 template <class BidiIterator, class Allocator, class traits>
1031 bool perl_matcher<BidiIterator, Allocator, traits>::match_commit()
1032 {
1033    m_can_backtrack = false;
1034    int action = static_cast<const re_commit*>(pstate)->action;
1035    switch(action)
1036    {
1037    case commit_commit:
1038       restart = last;
1039       break;
1040    case commit_skip:
1041       restart = position;
1042       break;
1043    }
1044    pstate = pstate->next.p;
1045    return true;
1046 }
1047
1048 template <class BidiIterator, class Allocator, class traits>
1049 bool perl_matcher<BidiIterator, Allocator, traits>::match_then()
1050 {
1051    pstate = pstate->next.p;
1052    if(match_all_states())
1053       return true;
1054    m_can_backtrack = false;
1055    m_have_then = true;
1056    return false;
1057 }
1058
1059 template <class BidiIterator, class Allocator, class traits>
1060 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
1061 {
1062    // change our case sensitivity:
1063    bool oldcase = this->icase;
1064    this->icase = static_cast<const re_case*>(pstate)->icase;
1065    pstate = pstate->next.p;
1066    bool result = match_all_states();
1067    this->icase = oldcase;
1068    return result;
1069 }
1070
1071
1072
1073 template <class BidiIterator, class Allocator, class traits>
1074 bool perl_matcher<BidiIterator, Allocator, traits>::skip_until_paren(int index, bool have_match)
1075 {
1076    while(pstate)
1077    {
1078       if(pstate->type == syntax_element_endmark)
1079       {
1080          if(static_cast<const re_brace*>(pstate)->index == index)
1081          {
1082             if(have_match)
1083                return this->match_endmark();
1084             pstate = pstate->next.p;
1085             return true;
1086          }
1087          else
1088          {
1089             // Unenclosed closing ), occurs when (*ACCEPT) is inside some other
1090             // parenthesis which may or may not have other side effects associated with it.
1091             bool r = match_endmark();
1092             m_have_accept = true;
1093             if(!pstate)
1094                return r;
1095          }
1096          continue;
1097       }
1098       else if(pstate->type == syntax_element_match)
1099          return true;
1100       else if(pstate->type == syntax_element_startmark)
1101       {
1102          int idx = static_cast<const re_brace*>(pstate)->index;
1103          pstate = pstate->next.p;
1104          skip_until_paren(idx, false);
1105          continue;
1106       }
1107       pstate = pstate->next.p;
1108    }
1109    return true;
1110 }
1111
1112
1113 } // namespace BOOST_REGEX_DETAIL_NS
1114 } // namespace boost
1115 #ifdef BOOST_MSVC
1116 #pragma warning(pop)
1117 #endif
1118
1119 #ifdef BOOST_MSVC
1120 #pragma warning(push)
1121 #pragma warning(disable: 4103)
1122 #endif
1123 #ifdef BOOST_HAS_ABI_HEADERS
1124 #  include BOOST_ABI_SUFFIX
1125 #endif
1126 #ifdef BOOST_MSVC
1127 #pragma warning(pop)
1128 #endif
1129
1130 #endif
1131