regex/v5/perl_matcher_non_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 non-recursive implementation.
0018   */
0019
0020 #ifndef BOOST_REGEX_V5_PERL_MATCHER_NON_RECURSIVE_HPP
0021 #define BOOST_REGEX_V5_PERL_MATCHER_NON_RECURSIVE_HPP
0022
0023 #include <boost/regex/v5/mem_block_cache.hpp>
0024
0025 #ifdef BOOST_REGEX_MSVC
0026 #  pragma warning(push)
0027 #  pragma warning(disable: 4706 4459)
0028 #if BOOST_REGEX_MSVC < 1910
0029 #pragma warning(disable:4800)
0030 #endif
0031 #endif
0032
0033 namespace boost{
0034 namespace BOOST_REGEX_DETAIL_NS{
0035
0036 template <class T>
0037 inline void inplace_destroy(T* p)
0038 {
0039    (void)p;  // warning suppression
0040    p->~T();
0041 }
0042
0043 struct saved_state
0044 {
0045    union{
0046       unsigned int state_id;
0047       // this padding ensures correct alignment on 64-bit platforms:
0048       std::size_t padding1;
0049       std::ptrdiff_t padding2;
0050       void* padding3;
0051    };
0052    saved_state(unsigned i) : state_id(i) {}
0053 };
0054
0055 template <class BidiIterator>
0056 struct saved_matched_paren : public saved_state
0057 {
0058    int index;
0059    sub_match<BidiIterator> sub;
0060    saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){}
0061 };
0062
0063 template <class BidiIterator>
0064 struct saved_position : public saved_state
0065 {
0066    const re_syntax_base* pstate;
0067    BidiIterator position;
0068    saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){}
0069 };
0070
0071 template <class BidiIterator>
0072 struct saved_assertion : public saved_position<BidiIterator>
0073 {
0074    bool positive;
0075    saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
0076       : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){}
0077 };
0078
0079 template <class BidiIterator>
0080 struct saved_repeater : public saved_state
0081 {
0082    repeater_count<BidiIterator> count;
0083    saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start, int current_recursion_id)
0084       : saved_state(saved_state_repeater_count), count(i, s, start, current_recursion_id){}
0085 };
0086
0087 struct saved_extra_block : public saved_state
0088 {
0089    saved_state *base, *end;
0090    saved_extra_block(saved_state* b, saved_state* e)
0091       : saved_state(saved_state_extra_block), base(b), end(e) {}
0092 };
0093
0094 struct save_state_init
0095 {
0096    saved_state** stack;
0097    save_state_init(saved_state** base, saved_state** end)
0098       : stack(base)
0099    {
0100       *base = static_cast<saved_state*>(get_mem_block());
0101       *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
0102       --(*end);
0103       (void) new (*end)saved_state(0);
0104       BOOST_REGEX_ASSERT(*end > *base);
0105    }
0106    ~save_state_init()
0107    {
0108       put_mem_block(*stack);
0109       *stack = 0;
0110    }
0111 };
0112
0113 template <class BidiIterator>
0114 struct saved_single_repeat : public saved_state
0115 {
0116    std::size_t count;
0117    const re_repeat* rep;
0118    BidiIterator last_position;
0119    saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
0120       : saved_state(arg_id), count(c), rep(r), last_position(lp){}
0121 };
0122
0123 template <class Results>
0124 struct saved_recursion : public saved_state
0125 {
0126    saved_recursion(int idx, const re_syntax_base* p, Results* pr, Results* pr2)
0127       : saved_state(14), recursion_id(idx), preturn_address(p), internal_results(*pr), prior_results(*pr2) {}
0128    int recursion_id;
0129    const re_syntax_base* preturn_address;
0130    Results internal_results, prior_results;
0131 };
0132
0133 struct saved_change_case : public saved_state
0134 {
0135    bool icase;
0136    saved_change_case(bool c) : saved_state(18), icase(c) {}
0137 };
0138
0139 struct incrementer
0140 {
0141    incrementer(unsigned* pu) : m_pu(pu) { ++*m_pu; }
0142    ~incrementer() { --*m_pu; }
0143    bool operator > (unsigned i) { return *m_pu > i; }
0144 private:
0145    unsigned* m_pu;
0146 };
0147
0148 template <class BidiIterator, class Allocator, class traits>
0149 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
0150 {
0151    static matcher_proc_type const s_match_vtable[34] =
0152    {
0153       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
0154       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
0155       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
0156       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
0157       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
0158       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
0159       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
0160       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
0161       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
0162       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
0163       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
0164       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
0165       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
0166       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
0167       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
0168       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
0169       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
0170       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
0171       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
0172       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
0173       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
0174       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
0175       // Although this next line *should* be evaluated at compile time, in practice
0176       // some compilers (VC++) emit run-time initialisation which breaks thread
0177       // safety, so use a dispatch function instead:
0178       //(::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),
0179       &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
0180       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
0181       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
0182       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
0183       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
0184       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
0185       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
0186       &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
0187       &perl_matcher<BidiIterator, Allocator, traits>::match_fail,
0188       &perl_matcher<BidiIterator, Allocator, traits>::match_accept,
0189       &perl_matcher<BidiIterator, Allocator, traits>::match_commit,
0190       &perl_matcher<BidiIterator, Allocator, traits>::match_then,
0191    };
0192    incrementer inc(&m_recursions);
0193    if(inc > 80)
0194       raise_error(traits_inst, regex_constants::error_complexity);
0195    push_recursion_stopper();
0196    do{
0197       while(pstate)
0198       {
0199          matcher_proc_type proc = s_match_vtable[pstate->type];
0200          ++state_count;
0201          if(!(this->*proc)())
0202          {
0203             if(state_count > max_state_count)
0204                raise_error(traits_inst, regex_constants::error_complexity);
0205             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
0206                m_has_partial_match = true;
0207             bool successful_unwind = unwind(false);
0208             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
0209                m_has_partial_match = true;
0210             if(!successful_unwind)
0211                return m_recursive_result;
0212          }
0213       }
0214    }while(unwind(true));
0215    return m_recursive_result;
0216 }
0217
0218 template <class BidiIterator, class Allocator, class traits>
0219 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
0220 {
0221    if(used_block_count)
0222    {
0223       --used_block_count;
0224       saved_state* stack_base;
0225       saved_state* backup_state;
0226       stack_base = static_cast<saved_state*>(get_mem_block());
0227       backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
0228       saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
0229       --block;
0230       (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
0231       m_stack_base = stack_base;
0232       m_backup_state = block;
0233    }
0234    else
0235       raise_error(traits_inst, regex_constants::error_stack);
0236 }
0237
0238 template <class BidiIterator, class Allocator, class traits>
0239 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
0240 {
0241    //BOOST_REGEX_ASSERT(index);
0242    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
0243    --pmp;
0244    if(pmp < m_stack_base)
0245    {
0246       extend_stack();
0247       pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
0248       --pmp;
0249    }
0250    (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
0251    m_backup_state = pmp;
0252 }
0253
0254 template <class BidiIterator, class Allocator, class traits>
0255 inline void perl_matcher<BidiIterator, Allocator, traits>::push_case_change(bool c)
0256 {
0257    //BOOST_REGEX_ASSERT(index);
0258    saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
0259    --pmp;
0260    if(pmp < m_stack_base)
0261    {
0262       extend_stack();
0263       pmp = static_cast<saved_change_case*>(m_backup_state);
0264       --pmp;
0265    }
0266    (void) new (pmp)saved_change_case(c);
0267    m_backup_state = pmp;
0268 }
0269
0270 template <class BidiIterator, class Allocator, class traits>
0271 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
0272 {
0273    saved_state* pmp = m_backup_state;
0274    --pmp;
0275    if(pmp < m_stack_base)
0276    {
0277       extend_stack();
0278       pmp = m_backup_state;
0279       --pmp;
0280    }
0281    (void) new (pmp)saved_state(saved_type_recurse);
0282    m_backup_state = pmp;
0283 }
0284
0285 template <class BidiIterator, class Allocator, class traits>
0286 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
0287 {
0288    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
0289    --pmp;
0290    if(pmp < m_stack_base)
0291    {
0292       extend_stack();
0293       pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
0294       --pmp;
0295    }
0296    (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
0297    m_backup_state = pmp;
0298 }
0299
0300 template <class BidiIterator, class Allocator, class traits>
0301 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
0302 {
0303    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
0304    --pmp;
0305    if(pmp < m_stack_base)
0306    {
0307       extend_stack();
0308       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
0309       --pmp;
0310    }
0311    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
0312    m_backup_state = pmp;
0313 }
0314
0315 template <class BidiIterator, class Allocator, class traits>
0316 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
0317 {
0318    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
0319    --pmp;
0320    if(pmp < m_stack_base)
0321    {
0322       extend_stack();
0323       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
0324       --pmp;
0325    }
0326    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
0327    m_backup_state = pmp;
0328 }
0329
0330 template <class BidiIterator, class Allocator, class traits>
0331 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
0332 {
0333    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
0334    --pmp;
0335    if(pmp < m_stack_base)
0336    {
0337       extend_stack();
0338       pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
0339       --pmp;
0340    }
0341    (void) new (pmp)saved_repeater<BidiIterator>(i, s, position, this->recursion_stack.empty() ? (INT_MIN + 3) : this->recursion_stack.back().idx);
0342    m_backup_state = pmp;
0343 }
0344
0345 template <class BidiIterator, class Allocator, class traits>
0346 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
0347 {
0348    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
0349    --pmp;
0350    if(pmp < m_stack_base)
0351    {
0352       extend_stack();
0353       pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
0354       --pmp;
0355    }
0356    (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
0357    m_backup_state = pmp;
0358 }
0359
0360 template <class BidiIterator, class Allocator, class traits>
0361 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int idx, const re_syntax_base* p, results_type* presults, results_type* presults2)
0362 {
0363    saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
0364    --pmp;
0365    if(pmp < m_stack_base)
0366    {
0367       extend_stack();
0368       pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
0369       --pmp;
0370    }
0371    (void) new (pmp)saved_recursion<results_type>(idx, p, presults, presults2);
0372    m_backup_state = pmp;
0373 }
0374
0375 template <class BidiIterator, class Allocator, class traits>
0376 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
0377 {
0378    // change our case sensitivity:
0379    push_case_change(this->icase);
0380    this->icase = static_cast<const re_case*>(pstate)->icase;
0381    pstate = pstate->next.p;
0382    return true;
0383 }
0384
0385 template <class BidiIterator, class Allocator, class traits>
0386 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
0387 {
0388    int index = static_cast<const re_brace*>(pstate)->index;
0389    icase = static_cast<const re_brace*>(pstate)->icase;
0390    switch(index)
0391    {
0392    case 0:
0393       pstate = pstate->next.p;
0394       break;
0395    case -1:
0396    case -2:
0397       {
0398          // forward lookahead assert:
0399          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
0400          pstate = pstate->next.p->next.p;
0401          push_assertion(next_pstate, index == -1);
0402          break;
0403       }
0404    case -3:
0405       {
0406          // independent sub-expression, currently this is always recursive:
0407          bool old_independent = m_independent;
0408          m_independent = true;
0409          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
0410          pstate = pstate->next.p->next.p;
0411          bool r = false;
0412 #if !defined(BOOST_NO_EXCEPTIONS)
0413       try{
0414 #endif
0415          r = match_all_states();
0416          if(!r && !m_independent)
0417          {
0418             // Must be unwinding from a COMMIT/SKIP/PRUNE and the independent
0419             // sub failed, need to unwind everything else:
0420             while (m_backup_state->state_id)
0421                unwind(false);
0422             return false;
0423          }
0424 #if !defined(BOOST_NO_EXCEPTIONS)
0425       }
0426       catch(...)
0427       {
0428          pstate = next_pstate;
0429          // unwind all pushed states, apart from anything else this
0430          // ensures that all the states are correctly destructed
0431          // not just the memory freed.
0432          while(unwind(true)) {}
0433          throw;
0434       }
0435 #endif
0436       pstate = next_pstate;
0437       m_independent = old_independent;
0438 #ifdef BOOST_REGEX_MATCH_EXTRA
0439          if(r && (m_match_flags & match_extra))
0440          {
0441             //
0442             // our captures have been stored in *m_presult
0443             // we need to unpack them, and insert them
0444             // back in the right order when we unwind the stack:
0445             //
0446             match_results<BidiIterator, Allocator> temp_match(*m_presult);
0447             unsigned i;
0448             for(i = 0; i < temp_match.size(); ++i)
0449                (*m_presult)[i].get_captures().clear();
0450             // match everything else:
0451 #if !defined(BOOST_NO_EXCEPTIONS)
0452             try{
0453 #endif
0454                r = match_all_states();
0455 #if !defined(BOOST_NO_EXCEPTIONS)
0456             }
0457             catch(...)
0458             {
0459                pstate = next_pstate;
0460                // unwind all pushed states, apart from anything else this
0461                // ensures that all the states are correctly destructed
0462                // not just the memory freed.
0463                while(unwind(true)) {}
0464                throw;
0465             }
0466 #endif
0467          // now place the stored captures back:
0468             for(i = 0; i < temp_match.size(); ++i)
0469             {
0470                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
0471                seq& s1 = (*m_presult)[i].get_captures();
0472                const seq& s2 = temp_match[i].captures();
0473                s1.insert(
0474                   s1.end(),
0475                   s2.begin(),
0476                   s2.end());
0477             }
0478          }
0479 #endif
0480          return r;
0481       }
0482    case -4:
0483       {
0484       // conditional expression:
0485       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
0486       BOOST_REGEX_ASSERT(alt->type == syntax_element_alt);
0487       pstate = alt->next.p;
0488       if(pstate->type == syntax_element_assert_backref)
0489       {
0490          if(!match_assert_backref())
0491             pstate = alt->alt.p;
0492          break;
0493       }
0494       else
0495       {
0496          // zero width assertion, have to match this recursively:
0497          BOOST_REGEX_ASSERT(pstate->type == syntax_element_startmark);
0498          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
0499          BidiIterator saved_position = position;
0500          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
0501          pstate = pstate->next.p->next.p;
0502 #if !defined(BOOST_NO_EXCEPTIONS)
0503          try{
0504 #endif
0505             bool r = match_all_states();
0506             position = saved_position;
0507             if(negated)
0508                r = !r;
0509             if(r)
0510                pstate = next_pstate;
0511             else
0512                pstate = alt->alt.p;
0513 #if !defined(BOOST_NO_EXCEPTIONS)
0514          }
0515          catch(...)
0516          {
0517             pstate = next_pstate;
0518             // unwind all pushed states, apart from anything else this
0519             // ensures that all the states are correctly destructed
0520             // not just the memory freed.
0521             while(unwind(true)){}
0522             throw;
0523          }
0524 #endif
0525          break;
0526       }
0527       }
0528    case -5:
0529       {
0530          push_matched_paren(0, (*m_presult)[0]);
0531          m_presult->set_first(position, 0, true);
0532          pstate = pstate->next.p;
0533          break;
0534       }
0535    default:
0536    {
0537       BOOST_REGEX_ASSERT(index > 0);
0538       if((m_match_flags & match_nosubs) == 0)
0539       {
0540          push_matched_paren(index, (*m_presult)[index]);
0541          m_presult->set_first(position, index);
0542       }
0543       pstate = pstate->next.p;
0544       break;
0545    }
0546    }
0547    return true;
0548 }
0549
0550 template <class BidiIterator, class Allocator, class traits>
0551 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
0552 {
0553    bool take_first, take_second;
0554    const re_alt* jmp = static_cast<const re_alt*>(pstate);
0555
0556    // find out which of these two alternatives we need to take:
0557    if(position == last)
0558    {
0559       take_first = jmp->can_be_null & mask_take;
0560       take_second = jmp->can_be_null & mask_skip;
0561    }
0562    else
0563    {
0564       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
0565       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
0566   }
0567
0568    if(take_first)
0569    {
0570       // we can take the first alternative,
0571       // see if we need to push next alternative:
0572       if(take_second)
0573       {
0574          push_alt(jmp->alt.p);
0575       }
0576       pstate = pstate->next.p;
0577       return true;
0578    }
0579    if(take_second)
0580    {
0581       pstate = jmp->alt.p;
0582       return true;
0583    }
0584    return false;  // neither option is possible
0585 }
0586
0587 template <class BidiIterator, class Allocator, class traits>
0588 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
0589 {
0590 #ifdef BOOST_REGEX_MSVC
0591 #pragma warning(push)
0592 #pragma warning(disable:4127 4244)
0593 #endif
0594 #ifdef BOOST_BORLANDC
0595 #pragma option push -w-8008 -w-8066 -w-8004
0596 #endif
0597    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0598
0599    // find out which of these two alternatives we need to take:
0600    bool take_first, take_second;
0601    if(position == last)
0602    {
0603       take_first = rep->can_be_null & mask_take;
0604       take_second = rep->can_be_null & mask_skip;
0605    }
0606    else
0607    {
0608       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
0609       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
0610    }
0611
0612    if((m_backup_state->state_id != saved_state_repeater_count)
0613       || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
0614       || (next_count->get_id() != rep->state_id))
0615    {
0616       // we're moving to a different repeat from the last
0617       // one, so set up a counter object:
0618       push_repeater_count(rep->state_id, &next_count);
0619    }
0620    //
0621    // If we've had at least one repeat already, and the last one
0622    // matched the NULL string then set the repeat count to
0623    // maximum:
0624    //
0625    next_count->check_null_repeat(position, rep->max);
0626
0627    if(next_count->get_count() < rep->min)
0628    {
0629       // we must take the repeat:
0630       if(take_first)
0631       {
0632          // increase the counter:
0633          ++(*next_count);
0634          pstate = rep->next.p;
0635          return true;
0636       }
0637       return false;
0638    }
0639
0640    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0641    if(greedy)
0642    {
0643       // try and take the repeat if we can:
0644       if((next_count->get_count() < rep->max) && take_first)
0645       {
0646          if(take_second)
0647          {
0648             // store position in case we fail:
0649             push_alt(rep->alt.p);
0650          }
0651          // increase the counter:
0652          ++(*next_count);
0653          pstate = rep->next.p;
0654          return true;
0655       }
0656       else if(take_second)
0657       {
0658          pstate = rep->alt.p;
0659          return true;
0660       }
0661       return false; // can't take anything, fail...
0662    }
0663    else // non-greedy
0664    {
0665       // try and skip the repeat if we can:
0666       if(take_second)
0667       {
0668          if((next_count->get_count() < rep->max) && take_first)
0669          {
0670             // store position in case we fail:
0671             push_non_greedy_repeat(rep->next.p);
0672          }
0673          pstate = rep->alt.p;
0674          return true;
0675       }
0676       if((next_count->get_count() < rep->max) && take_first)
0677       {
0678          // increase the counter:
0679          ++(*next_count);
0680          pstate = rep->next.p;
0681          return true;
0682       }
0683    }
0684    return false;
0685 #ifdef BOOST_BORLANDC
0686 #pragma option pop
0687 #endif
0688 #ifdef BOOST_REGEX_MSVC
0689 #pragma warning(pop)
0690 #endif
0691 }
0692
0693 template <class BidiIterator, class Allocator, class traits>
0694 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
0695 {
0696    std::size_t count = 0;
0697    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0698    re_syntax_base* psingle = rep->next.p;
0699    // match compulsory repeats first:
0700    while(count < rep->min)
0701    {
0702       pstate = psingle;
0703       if(!match_wild())
0704          return false;
0705       ++count;
0706    }
0707    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0708    if(greedy)
0709    {
0710       // repeat for as long as we can:
0711       while(count < rep->max)
0712       {
0713          pstate = psingle;
0714          if(!match_wild())
0715             break;
0716          ++count;
0717       }
0718       // remember where we got to if this is a leading repeat:
0719       if((rep->leading) && (count < rep->max))
0720          restart = position;
0721       // push backtrack info if available:
0722       if(count - rep->min)
0723          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
0724       // jump to next state:
0725       pstate = rep->alt.p;
0726       return true;
0727    }
0728    else
0729    {
0730       // non-greedy, push state and return true if we can skip:
0731       if(count < rep->max)
0732          push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
0733       pstate = rep->alt.p;
0734       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
0735    }
0736 }
0737
0738 template <class BidiIterator, class Allocator, class traits>
0739 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
0740 {
0741    if(m_match_flags & match_not_dot_null)
0742       return match_dot_repeat_slow();
0743    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
0744       return match_dot_repeat_slow();
0745
0746    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0747    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0748    std::size_t count = static_cast<std::size_t>((std::min)(static_cast<std::size_t>(std::distance(position, last)), greedy ? rep->max : rep->min));
0749    if(rep->min > count)
0750    {
0751       position = last;
0752       return false;  // not enough text left to match
0753    }
0754    std::advance(position, count);
0755
0756    if(greedy)
0757    {
0758       if((rep->leading) && (count < rep->max))
0759          restart = position;
0760       // push backtrack info if available:
0761       if(count - rep->min)
0762          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
0763       // jump to next state:
0764       pstate = rep->alt.p;
0765       return true;
0766    }
0767    else
0768    {
0769       // non-greedy, push state and return true if we can skip:
0770       if(count < rep->max)
0771          push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
0772       pstate = rep->alt.p;
0773       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
0774    }
0775 }
0776
0777 template <class BidiIterator, class Allocator, class traits>
0778 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
0779 {
0780 #ifdef BOOST_REGEX_MSVC
0781 #pragma warning(push)
0782 #pragma warning(disable:4127)
0783 #endif
0784 #ifdef BOOST_BORLANDC
0785 #pragma option push -w-8008 -w-8066 -w-8004
0786 #endif
0787    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0788    BOOST_REGEX_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
0789    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
0790    std::size_t count = 0;
0791    //
0792    // start by working out how much we can skip:
0793    //
0794    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0795    std::size_t desired = greedy ? rep->max : rep->min;
0796    if(::boost::is_random_access_iterator<BidiIterator>::value)
0797    {
0798       BidiIterator end = position;
0799       // Move end forward by "desired", preferably without using distance or advance if we can
0800       // as these can be slow for some iterator types.
0801       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
0802       if(desired >= len)
0803          end = last;
0804       else
0805          std::advance(end, desired);
0806       BidiIterator origin(position);
0807       while((position != end) && (traits_inst.translate(*position, icase) == what))
0808       {
0809          ++position;
0810       }
0811       count = (unsigned)std::distance(origin, position);
0812    }
0813    else
0814    {
0815       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
0816       {
0817          ++position;
0818          ++count;
0819       }
0820    }
0821
0822    if(count < rep->min)
0823       return false;
0824
0825    if(greedy)
0826    {
0827       if((rep->leading) && (count < rep->max))
0828          restart = position;
0829       // push backtrack info if available:
0830       if(count - rep->min)
0831          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
0832       // jump to next state:
0833       pstate = rep->alt.p;
0834       return true;
0835    }
0836    else
0837    {
0838       // non-greedy, push state and return true if we can skip:
0839       if(count < rep->max)
0840          push_single_repeat(count, rep, position, saved_state_rep_char);
0841       pstate = rep->alt.p;
0842       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
0843    }
0844 #ifdef BOOST_BORLANDC
0845 #pragma option pop
0846 #endif
0847 #ifdef BOOST_REGEX_MSVC
0848 #pragma warning(pop)
0849 #endif
0850 }
0851
0852 template <class BidiIterator, class Allocator, class traits>
0853 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
0854 {
0855 #ifdef BOOST_REGEX_MSVC
0856 #pragma warning(push)
0857 #pragma warning(disable:4127)
0858 #endif
0859 #ifdef BOOST_BORLANDC
0860 #pragma option push -w-8008 -w-8066 -w-8004
0861 #endif
0862    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0863    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
0864    std::size_t count = 0;
0865    //
0866    // start by working out how much we can skip:
0867    //
0868    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0869    std::size_t desired = greedy ? rep->max : rep->min;
0870    if(::boost::is_random_access_iterator<BidiIterator>::value)
0871    {
0872       BidiIterator end = position;
0873       // Move end forward by "desired", preferably without using distance or advance if we can
0874       // as these can be slow for some iterator types.
0875       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
0876       if(desired >= len)
0877          end = last;
0878       else
0879          std::advance(end, desired);
0880       BidiIterator origin(position);
0881       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0882       {
0883          ++position;
0884       }
0885       count = (unsigned)std::distance(origin, position);
0886    }
0887    else
0888    {
0889       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
0890       {
0891          ++position;
0892          ++count;
0893       }
0894    }
0895
0896    if(count < rep->min)
0897       return false;
0898
0899    if(greedy)
0900    {
0901       if((rep->leading) && (count < rep->max))
0902          restart = position;
0903       // push backtrack info if available:
0904       if(count - rep->min)
0905          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
0906       // jump to next state:
0907       pstate = rep->alt.p;
0908       return true;
0909    }
0910    else
0911    {
0912       // non-greedy, push state and return true if we can skip:
0913       if(count < rep->max)
0914          push_single_repeat(count, rep, position, saved_state_rep_short_set);
0915       pstate = rep->alt.p;
0916       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
0917    }
0918 #ifdef BOOST_BORLANDC
0919 #pragma option pop
0920 #endif
0921 #ifdef BOOST_REGEX_MSVC
0922 #pragma warning(pop)
0923 #endif
0924 }
0925
0926 template <class BidiIterator, class Allocator, class traits>
0927 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
0928 {
0929 #ifdef BOOST_REGEX_MSVC
0930 #pragma warning(push)
0931 #pragma warning(disable:4127)
0932 #endif
0933 #ifdef BOOST_BORLANDC
0934 #pragma option push -w-8008 -w-8066 -w-8004
0935 #endif
0936    typedef typename traits::char_class_type m_type;
0937    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
0938    const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate->next.p);
0939    std::size_t count = 0;
0940    //
0941    // start by working out how much we can skip:
0942    //
0943    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
0944    std::size_t desired = greedy ? rep->max : rep->min;
0945    if(::boost::is_random_access_iterator<BidiIterator>::value)
0946    {
0947       BidiIterator end = position;
0948       // Move end forward by "desired", preferably without using distance or advance if we can
0949       // as these can be slow for some iterator types.
0950       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
0951       if(desired >= len)
0952          end = last;
0953       else
0954          std::advance(end, desired);
0955       BidiIterator origin(position);
0956       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
0957       {
0958          ++position;
0959       }
0960       count = (unsigned)std::distance(origin, position);
0961    }
0962    else
0963    {
0964       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
0965       {
0966          ++position;
0967          ++count;
0968       }
0969    }
0970
0971    if(count < rep->min)
0972       return false;
0973
0974    if(greedy)
0975    {
0976       if((rep->leading) && (count < rep->max))
0977          restart = position;
0978       // push backtrack info if available:
0979       if(count - rep->min)
0980          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
0981       // jump to next state:
0982       pstate = rep->alt.p;
0983       return true;
0984    }
0985    else
0986    {
0987       // non-greedy, push state and return true if we can skip:
0988       if(count < rep->max)
0989          push_single_repeat(count, rep, position, saved_state_rep_long_set);
0990       pstate = rep->alt.p;
0991       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
0992    }
0993 #ifdef BOOST_BORLANDC
0994 #pragma option pop
0995 #endif
0996 #ifdef BOOST_REGEX_MSVC
0997 #pragma warning(pop)
0998 #endif
0999 }
1000
1001 template <class BidiIterator, class Allocator, class traits>
1002 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
1003 {
1004    BOOST_REGEX_ASSERT(pstate->type == syntax_element_recurse);
1005    //
1006    // See if we've seen this recursion before at this location, if we have then
1007    // we need to prevent infinite recursion:
1008    //
1009    for(typename std::vector<recursion_info<results_type> >::reverse_iterator i = recursion_stack.rbegin(); i != recursion_stack.rend(); ++i)
1010    {
1011       if(i->idx == static_cast<const re_brace*>(static_cast<const re_jump*>(pstate)->alt.p)->index)
1012       {
1013          if(i->location_of_start == position)
1014             return false;
1015          break;
1016       }
1017    }
1018    //
1019    // Backup call stack:
1020    //
1021    push_recursion_pop();
1022    //
1023    // Set new call stack:
1024    //
1025    if(recursion_stack.capacity() == 0)
1026    {
1027       recursion_stack.reserve(50);
1028    }
1029    recursion_stack.push_back(recursion_info<results_type>());
1030    recursion_stack.back().preturn_address = pstate->next.p;
1031    recursion_stack.back().results = *m_presult;
1032    pstate = static_cast<const re_jump*>(pstate)->alt.p;
1033    recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
1034    recursion_stack.back().location_of_start = position;
1035    //if(static_cast<const re_recurse*>(pstate)->state_id > 0)
1036    {
1037       push_repeater_count(-(2 + static_cast<const re_brace*>(pstate)->index), &next_count);
1038    }
1039
1040    return true;
1041 }
1042
1043 template <class BidiIterator, class Allocator, class traits>
1044 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
1045 {
1046    int index = static_cast<const re_brace*>(pstate)->index;
1047    icase = static_cast<const re_brace*>(pstate)->icase;
1048    if(index > 0)
1049    {
1050       if((m_match_flags & match_nosubs) == 0)
1051       {
1052          m_presult->set_second(position, index);
1053       }
1054       if(!recursion_stack.empty())
1055       {
1056          if(index == recursion_stack.back().idx)
1057          {
1058             pstate = recursion_stack.back().preturn_address;
1059             *m_presult = recursion_stack.back().results;
1060             push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, m_presult, &recursion_stack.back().results);
1061             recursion_stack.pop_back();
1062             push_repeater_count(-(2 + index), &next_count);
1063          }
1064       }
1065    }
1066    else if((index < 0) && (index != -4))
1067    {
1068       // matched forward lookahead:
1069       pstate = 0;
1070       return true;
1071    }
1072    pstate = pstate->next.p;
1073    return true;
1074 }
1075
1076 template <class BidiIterator, class Allocator, class traits>
1077 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
1078 {
1079    if(!recursion_stack.empty())
1080    {
1081       BOOST_REGEX_ASSERT(0 == recursion_stack.back().idx);
1082       pstate = recursion_stack.back().preturn_address;
1083       push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, m_presult, &recursion_stack.back().results);
1084       *m_presult = recursion_stack.back().results;
1085       recursion_stack.pop_back();
1086       return true;
1087    }
1088    if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
1089       return false;
1090    if((m_match_flags & match_all) && (position != last))
1091       return false;
1092    if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
1093       return false;
1094    m_presult->set_second(position);
1095    pstate = 0;
1096    m_has_found_match = true;
1097    if((m_match_flags & match_posix) == match_posix)
1098    {
1099       m_result.maybe_assign(*m_presult);
1100       if((m_match_flags & match_any) == 0)
1101          return false;
1102    }
1103 #ifdef BOOST_REGEX_MATCH_EXTRA
1104    if(match_extra & m_match_flags)
1105    {
1106       for(unsigned i = 0; i < m_presult->size(); ++i)
1107          if((*m_presult)[i].matched)
1108             ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
1109    }
1110 #endif
1111    return true;
1112 }
1113
1114 template <class BidiIterator, class Allocator, class traits>
1115 bool perl_matcher<BidiIterator, Allocator, traits>::match_commit()
1116 {
1117    // Ideally we would just junk all the states that are on the stack,
1118    // however we might not unwind correctly in that case, so for now,
1119    // just mark that we don't backtrack into whatever is left (or rather
1120    // we'll unwind it unconditionally without pausing to try other matches).
1121
1122    switch(static_cast<const re_commit*>(pstate)->action)
1123    {
1124    case commit_commit:
1125       restart = last;
1126       break;
1127    case commit_skip:
1128       if(base != position)
1129       {
1130          restart = position;
1131          // Have to decrement restart since it will get incremented again later:
1132          --restart;
1133       }
1134       break;
1135    case commit_prune:
1136       break;
1137    }
1138
1139    saved_state* pmp = m_backup_state;
1140    --pmp;
1141    if(pmp < m_stack_base)
1142    {
1143       extend_stack();
1144       pmp = m_backup_state;
1145       --pmp;
1146    }
1147    (void) new (pmp)saved_state(16);
1148    m_backup_state = pmp;
1149    pstate = pstate->next.p;
1150    return true;
1151 }
1152
1153 template <class BidiIterator, class Allocator, class traits>
1154 bool perl_matcher<BidiIterator, Allocator, traits>::match_then()
1155 {
1156    // Just leave a mark that we need to skip to next alternative:
1157    saved_state* pmp = m_backup_state;
1158    --pmp;
1159    if(pmp < m_stack_base)
1160    {
1161       extend_stack();
1162       pmp = m_backup_state;
1163       --pmp;
1164    }
1165    (void) new (pmp)saved_state(17);
1166    m_backup_state = pmp;
1167    pstate = pstate->next.p;
1168    return true;
1169 }
1170
1171 template <class BidiIterator, class Allocator, class traits>
1172 bool perl_matcher<BidiIterator, Allocator, traits>::skip_until_paren(int index, bool have_match)
1173 {
1174    while(pstate)
1175    {
1176       if(pstate->type == syntax_element_endmark)
1177       {
1178          if(static_cast<const re_brace*>(pstate)->index == index)
1179          {
1180             if(have_match)
1181                return this->match_endmark();
1182             pstate = pstate->next.p;
1183             return true;
1184          }
1185          else
1186          {
1187             // Unenclosed closing ), occurs when (*ACCEPT) is inside some other
1188             // parenthesis which may or may not have other side effects associated with it.
1189             const re_syntax_base* sp = pstate;
1190             match_endmark();
1191             if(!pstate)
1192             {
1193                unwind(true);
1194                // unwind may leave pstate NULL if we've unwound a forward lookahead, in which
1195                // case just move to the next state and keep looking...
1196                if (!pstate)
1197                   pstate = sp->next.p;
1198             }
1199          }
1200          continue;
1201       }
1202       else if(pstate->type == syntax_element_match)
1203          return true;
1204       else if(pstate->type == syntax_element_startmark)
1205       {
1206          int idx = static_cast<const re_brace*>(pstate)->index;
1207          pstate = pstate->next.p;
1208          skip_until_paren(idx, false);
1209          continue;
1210       }
1211       pstate = pstate->next.p;
1212    }
1213    return true;
1214 }
1215
1216 /****************************************************************************
1217
1218 Unwind and associated procedures follow, these perform what normal stack
1219 unwinding does in the recursive implementation.
1220
1221 ****************************************************************************/
1222
1223 template <class BidiIterator, class Allocator, class traits>
1224 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
1225 {
1226    static unwind_proc_type const s_unwind_table[19] =
1227    {
1228       &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
1229       &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
1230       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
1231       &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
1232       &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
1233       &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
1234       &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
1235       &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
1236       &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
1237       &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
1238       &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
1239       &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
1240       &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
1241       &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
1242       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion,
1243       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop,
1244       &perl_matcher<BidiIterator, Allocator, traits>::unwind_commit,
1245       &perl_matcher<BidiIterator, Allocator, traits>::unwind_then,
1246       &perl_matcher<BidiIterator, Allocator, traits>::unwind_case,
1247    };
1248
1249    m_recursive_result = have_match;
1250    m_unwound_lookahead = false;
1251    m_unwound_alt = false;
1252    unwind_proc_type unwinder;
1253    bool cont;
1254    //
1255    // keep unwinding our stack until we have something to do:
1256    //
1257    do
1258    {
1259       unwinder = s_unwind_table[m_backup_state->state_id];
1260       cont = (this->*unwinder)(m_recursive_result);
1261    }while(cont);
1262    //
1263    // return true if we have more states to try:
1264    //
1265    return pstate ? true : false;
1266 }
1267
1268 template <class BidiIterator, class Allocator, class traits>
1269 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
1270 {
1271    pstate = 0;   // nothing left to search
1272    return false; // end of stack nothing more to search
1273 }
1274
1275 template <class BidiIterator, class Allocator, class traits>
1276 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_case(bool)
1277 {
1278    saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
1279    icase = pmp->icase;
1280    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1281    m_backup_state = pmp;
1282    return true;
1283 }
1284
1285 template <class BidiIterator, class Allocator, class traits>
1286 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
1287 {
1288    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
1289    // restore previous values if no match was found:
1290    if(!have_match)
1291    {
1292       m_presult->set_first(pmp->sub.first, pmp->index, pmp->index == 0);
1293       m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched, pmp->index == 0);
1294    }
1295 #ifdef BOOST_REGEX_MATCH_EXTRA
1296    //
1297    // we have a match, push the capture information onto the stack:
1298    //
1299    else if(pmp->sub.matched && (match_extra & m_match_flags))
1300       ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
1301 #endif
1302    // unwind stack:
1303    m_backup_state = pmp+1;
1304    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1305    return true; // keep looking
1306 }
1307
1308 template <class BidiIterator, class Allocator, class traits>
1309 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
1310 {
1311    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1312    pstate = 0;   // nothing left to search
1313    return false; // end of stack nothing more to search
1314 }
1315
1316 template <class BidiIterator, class Allocator, class traits>
1317 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
1318 {
1319    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
1320    pstate = pmp->pstate;
1321    position = pmp->position;
1322    bool result = (r == pmp->positive);
1323    m_recursive_result = pmp->positive ? r : !r;
1324    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1325    m_backup_state = pmp;
1326    m_unwound_lookahead = true;
1327    return !result; // return false if the assertion was matched to stop search.
1328 }
1329
1330 template <class BidiIterator, class Allocator, class traits>
1331 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
1332 {
1333    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1334    if(!r)
1335    {
1336       pstate = pmp->pstate;
1337       position = pmp->position;
1338    }
1339    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1340    m_backup_state = pmp;
1341    m_unwound_alt = !r;
1342    return r;
1343 }
1344
1345 template <class BidiIterator, class Allocator, class traits>
1346 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
1347 {
1348    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
1349    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1350    m_backup_state = pmp;
1351    return true; // keep looking
1352 }
1353
1354 template <class BidiIterator, class Allocator, class traits>
1355 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
1356 {
1357    ++used_block_count;
1358    saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
1359    void* condemmed = m_stack_base;
1360    m_stack_base = pmp->base;
1361    m_backup_state = pmp->end;
1362    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1363    put_mem_block(condemmed);
1364    return true; // keep looking
1365 }
1366
1367 template <class BidiIterator, class Allocator, class traits>
1368 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
1369 {
1370    saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1371    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(p++);
1372    m_backup_state = p;
1373 }
1374
1375 template <class BidiIterator, class Allocator, class traits>
1376 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
1377 {
1378    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1379
1380    // if we have a match, just discard this state:
1381    if(r)
1382    {
1383       destroy_single_repeat();
1384       return true;
1385    }
1386
1387    const re_repeat* rep = pmp->rep;
1388    std::size_t count = pmp->count;
1389    BOOST_REGEX_ASSERT(rep->next.p != 0);
1390    BOOST_REGEX_ASSERT(rep->alt.p != 0);
1391
1392    count -= rep->min;
1393
1394    if((m_match_flags & match_partial) && (position == last))
1395       m_has_partial_match = true;
1396
1397    BOOST_REGEX_ASSERT(count);
1398    position = pmp->last_position;
1399
1400    // backtrack till we can skip out:
1401    do
1402    {
1403       --position;
1404       --count;
1405       ++state_count;
1406    }while(count && !can_start(*position, rep->_map, mask_skip));
1407
1408    // if we've hit base, destroy this state:
1409    if(count == 0)
1410    {
1411          destroy_single_repeat();
1412          if(!can_start(*position, rep->_map, mask_skip))
1413             return true;
1414    }
1415    else
1416    {
1417       pmp->count = count + rep->min;
1418       pmp->last_position = position;
1419    }
1420    pstate = rep->alt.p;
1421    return false;
1422 }
1423
1424 template <class BidiIterator, class Allocator, class traits>
1425 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1426 {
1427    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1428
1429    // if we have a match, just discard this state:
1430    if(r)
1431    {
1432       destroy_single_repeat();
1433       return true;
1434    }
1435
1436    const re_repeat* rep = pmp->rep;
1437    std::size_t count = pmp->count;
1438    BOOST_REGEX_ASSERT(rep->type == syntax_element_dot_rep);
1439    BOOST_REGEX_ASSERT(rep->next.p != 0);
1440    BOOST_REGEX_ASSERT(rep->alt.p != 0);
1441    BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_wild);
1442
1443    BOOST_REGEX_ASSERT(count < rep->max);
1444    pstate = rep->next.p;
1445    position = pmp->last_position;
1446
1447    if(position != last)
1448    {
1449       // wind forward until we can skip out of the repeat:
1450       do
1451       {
1452          if(!match_wild())
1453          {
1454             // failed repeat match, discard this state and look for another:
1455             destroy_single_repeat();
1456             return true;
1457          }
1458          ++count;
1459          ++state_count;
1460          pstate = rep->next.p;
1461       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1462    }
1463    if(position == last)
1464    {
1465       // can't repeat any more, remove the pushed state:
1466       destroy_single_repeat();
1467       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1468          m_has_partial_match = true;
1469       if(0 == (rep->can_be_null & mask_skip))
1470          return true;
1471    }
1472    else if(count == rep->max)
1473    {
1474       // can't repeat any more, remove the pushed state:
1475       destroy_single_repeat();
1476       if(!can_start(*position, rep->_map, mask_skip))
1477          return true;
1478    }
1479    else
1480    {
1481       pmp->count = count;
1482       pmp->last_position = position;
1483    }
1484    pstate = rep->alt.p;
1485    return false;
1486 }
1487
1488 template <class BidiIterator, class Allocator, class traits>
1489 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1490 {
1491    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1492
1493    // if we have a match, just discard this state:
1494    if(r)
1495    {
1496       destroy_single_repeat();
1497       return true;
1498    }
1499
1500    const re_repeat* rep = pmp->rep;
1501    std::size_t count = pmp->count;
1502
1503    BOOST_REGEX_ASSERT(count < rep->max);
1504    position = pmp->last_position;
1505    if(position != last)
1506    {
1507
1508       // wind forward until we can skip out of the repeat:
1509       do
1510       {
1511          ++position;
1512          ++count;
1513          ++state_count;
1514       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1515    }
1516
1517    // remember where we got to if this is a leading repeat:
1518    if((rep->leading) && (count < rep->max))
1519       restart = position;
1520    if(position == last)
1521    {
1522       // can't repeat any more, remove the pushed state:
1523       destroy_single_repeat();
1524       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1525          m_has_partial_match = true;
1526       if(0 == (rep->can_be_null & mask_skip))
1527          return true;
1528    }
1529    else if(count == rep->max)
1530    {
1531       // can't repeat any more, remove the pushed state:
1532       destroy_single_repeat();
1533       if(!can_start(*position, rep->_map, mask_skip))
1534          return true;
1535    }
1536    else
1537    {
1538       pmp->count = count;
1539       pmp->last_position = position;
1540    }
1541    pstate = rep->alt.p;
1542    return false;
1543 }
1544
1545 template <class BidiIterator, class Allocator, class traits>
1546 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1547 {
1548    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1549
1550    // if we have a match, just discard this state:
1551    if(r)
1552    {
1553       destroy_single_repeat();
1554       return true;
1555    }
1556
1557    const re_repeat* rep = pmp->rep;
1558    std::size_t count = pmp->count;
1559    pstate = rep->next.p;
1560    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1561    position = pmp->last_position;
1562
1563    BOOST_REGEX_ASSERT(rep->type == syntax_element_char_rep);
1564    BOOST_REGEX_ASSERT(rep->next.p != 0);
1565    BOOST_REGEX_ASSERT(rep->alt.p != 0);
1566    BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_literal);
1567    BOOST_REGEX_ASSERT(count < rep->max);
1568
1569    if(position != last)
1570    {
1571       // wind forward until we can skip out of the repeat:
1572       do
1573       {
1574          if(traits_inst.translate(*position, icase) != what)
1575          {
1576             // failed repeat match, discard this state and look for another:
1577             destroy_single_repeat();
1578             return true;
1579          }
1580          ++count;
1581          ++ position;
1582          ++state_count;
1583          pstate = rep->next.p;
1584       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1585    }
1586    // remember where we got to if this is a leading repeat:
1587    if((rep->leading) && (count < rep->max))
1588       restart = position;
1589    if(position == last)
1590    {
1591       // can't repeat any more, remove the pushed state:
1592       destroy_single_repeat();
1593       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1594          m_has_partial_match = true;
1595       if(0 == (rep->can_be_null & mask_skip))
1596          return true;
1597    }
1598    else if(count == rep->max)
1599    {
1600       // can't repeat any more, remove the pushed state:
1601       destroy_single_repeat();
1602       if(!can_start(*position, rep->_map, mask_skip))
1603          return true;
1604    }
1605    else
1606    {
1607       pmp->count = count;
1608       pmp->last_position = position;
1609    }
1610    pstate = rep->alt.p;
1611    return false;
1612 }
1613
1614 template <class BidiIterator, class Allocator, class traits>
1615 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1616 {
1617    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1618
1619    // if we have a match, just discard this state:
1620    if(r)
1621    {
1622       destroy_single_repeat();
1623       return true;
1624    }
1625
1626    const re_repeat* rep = pmp->rep;
1627    std::size_t count = pmp->count;
1628    pstate = rep->next.p;
1629    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1630    position = pmp->last_position;
1631
1632    BOOST_REGEX_ASSERT(rep->type == syntax_element_short_set_rep);
1633    BOOST_REGEX_ASSERT(rep->next.p != 0);
1634    BOOST_REGEX_ASSERT(rep->alt.p != 0);
1635    BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_set);
1636    BOOST_REGEX_ASSERT(count < rep->max);
1637
1638    if(position != last)
1639    {
1640       // wind forward until we can skip out of the repeat:
1641       do
1642       {
1643          if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1644          {
1645             // failed repeat match, discard this state and look for another:
1646             destroy_single_repeat();
1647             return true;
1648          }
1649          ++count;
1650          ++ position;
1651          ++state_count;
1652          pstate = rep->next.p;
1653       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1654    }
1655    // remember where we got to if this is a leading repeat:
1656    if((rep->leading) && (count < rep->max))
1657       restart = position;
1658    if(position == last)
1659    {
1660       // can't repeat any more, remove the pushed state:
1661       destroy_single_repeat();
1662       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1663          m_has_partial_match = true;
1664       if(0 == (rep->can_be_null & mask_skip))
1665          return true;
1666    }
1667    else if(count == rep->max)
1668    {
1669       // can't repeat any more, remove the pushed state:
1670       destroy_single_repeat();
1671       if(!can_start(*position, rep->_map, mask_skip))
1672          return true;
1673    }
1674    else
1675    {
1676       pmp->count = count;
1677       pmp->last_position = position;
1678    }
1679    pstate = rep->alt.p;
1680    return false;
1681 }
1682
1683 template <class BidiIterator, class Allocator, class traits>
1684 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1685 {
1686    typedef typename traits::char_class_type m_type;
1687    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1688
1689    // if we have a match, just discard this state:
1690    if(r)
1691    {
1692       destroy_single_repeat();
1693       return true;
1694    }
1695
1696    const re_repeat* rep = pmp->rep;
1697    std::size_t count = pmp->count;
1698    pstate = rep->next.p;
1699    const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate);
1700    position = pmp->last_position;
1701
1702    BOOST_REGEX_ASSERT(rep->type == syntax_element_long_set_rep);
1703    BOOST_REGEX_ASSERT(rep->next.p != 0);
1704    BOOST_REGEX_ASSERT(rep->alt.p != 0);
1705    BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_long_set);
1706    BOOST_REGEX_ASSERT(count < rep->max);
1707
1708    if(position != last)
1709    {
1710       // wind forward until we can skip out of the repeat:
1711       do
1712       {
1713          if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1714          {
1715             // failed repeat match, discard this state and look for another:
1716             destroy_single_repeat();
1717             return true;
1718          }
1719          ++position;
1720          ++count;
1721          ++state_count;
1722          pstate = rep->next.p;
1723       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1724    }
1725    // remember where we got to if this is a leading repeat:
1726    if((rep->leading) && (count < rep->max))
1727       restart = position;
1728    if(position == last)
1729    {
1730       // can't repeat any more, remove the pushed state:
1731       destroy_single_repeat();
1732       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1733          m_has_partial_match = true;
1734       if(0 == (rep->can_be_null & mask_skip))
1735          return true;
1736    }
1737    else if(count == rep->max)
1738    {
1739       // can't repeat any more, remove the pushed state:
1740       destroy_single_repeat();
1741       if(!can_start(*position, rep->_map, mask_skip))
1742          return true;
1743    }
1744    else
1745    {
1746       pmp->count = count;
1747       pmp->last_position = position;
1748    }
1749    pstate = rep->alt.p;
1750    return false;
1751 }
1752
1753 template <class BidiIterator, class Allocator, class traits>
1754 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1755 {
1756    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1757    if(!r)
1758    {
1759       position = pmp->position;
1760       pstate = pmp->pstate;
1761       ++(*next_count);
1762    }
1763    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1764    m_backup_state = pmp;
1765    return r;
1766 }
1767
1768 template <class BidiIterator, class Allocator, class traits>
1769 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion(bool r)
1770 {
1771    // We are backtracking back inside a recursion, need to push the info
1772    // back onto the recursion stack, and do so unconditionally, otherwise
1773    // we can get mismatched pushes and pops...
1774    saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
1775    if (!r)
1776    {
1777       recursion_stack.push_back(recursion_info<results_type>());
1778       recursion_stack.back().idx = pmp->recursion_id;
1779       recursion_stack.back().preturn_address = pmp->preturn_address;
1780       recursion_stack.back().results = pmp->prior_results;
1781       recursion_stack.back().location_of_start = position;
1782       *m_presult = pmp->internal_results;
1783    }
1784    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1785    m_backup_state = pmp;
1786    return true;
1787 }
1788
1789 template <class BidiIterator, class Allocator, class traits>
1790 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop(bool r)
1791 {
1792    // Backtracking out of a recursion, we must pop state off the recursion
1793    // stack unconditionally to ensure matched pushes and pops:
1794    saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1795    if (!r && !recursion_stack.empty())
1796    {
1797       *m_presult = recursion_stack.back().results;
1798       position = recursion_stack.back().location_of_start;
1799       recursion_stack.pop_back();
1800    }
1801    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1802    m_backup_state = pmp;
1803    return true;
1804 }
1805
1806 template <class BidiIterator, class Allocator, class traits>
1807 void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_pop()
1808 {
1809    saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1810    --pmp;
1811    if(pmp < m_stack_base)
1812    {
1813       extend_stack();
1814       pmp = static_cast<saved_state*>(m_backup_state);
1815       --pmp;
1816    }
1817    (void) new (pmp)saved_state(15);
1818    m_backup_state = pmp;
1819 }
1820
1821 template <class BidiIterator, class Allocator, class traits>
1822 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_commit(bool b)
1823 {
1824    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1825    while(unwind(b) && !m_unwound_lookahead){}
1826    if(m_unwound_lookahead && pstate)
1827    {
1828       //
1829       // If we stop because we just unwound an assertion, put the
1830       // commit state back on the stack again:
1831       //
1832       m_unwound_lookahead = false;
1833       saved_state* pmp = m_backup_state;
1834       --pmp;
1835       if(pmp < m_stack_base)
1836       {
1837          extend_stack();
1838          pmp = m_backup_state;
1839          --pmp;
1840       }
1841       (void) new (pmp)saved_state(16);
1842       m_backup_state = pmp;
1843    }
1844    // This prevents us from stopping when we exit from an independent sub-expression:
1845    m_independent = false;
1846    return false;
1847 }
1848
1849 template <class BidiIterator, class Allocator, class traits>
1850 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_then(bool b)
1851 {
1852    // Unwind everything till we hit an alternative:
1853    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1854    bool result = false;
1855    result = unwind(b);
1856    while(result && !m_unwound_alt)
1857    {
1858       result = unwind(b);
1859    }
1860    // We're now pointing at the next alternative, need one more backtrack
1861    // since *all* the other alternatives must fail once we've reached a THEN clause:
1862    if(result && m_unwound_alt)
1863       unwind(b);
1864    return false;
1865 }
1866
1867 } // namespace BOOST_REGEX_DETAIL_NS
1868 } // namespace boost
1869
1870 #ifdef BOOST_REGEX_MSVC
1871 #  pragma warning(pop)
1872 #endif
1873
1874 #endif