ceph/src/boost/boost/regex/v5/perl_matcher_non_recursive.hpp

   1 /*
   2  *
   3  * Copyright (c) 2002
   4  * John Maddock
   5  *
   6  * Use, modification and distribution are subject to the
   7  * Boost Software License, Version 1.0. (See accompanying file
   8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9  *
  10  */
  11
  12  /*
  13   *   LOCATION:    see http://www.boost.org for most recent version.
  14   *   FILE         perl_matcher_common.cpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Definitions of perl_matcher member functions that are
  17   *                specific to the non-recursive implementation.
  18   */
  19
  20 #ifndef BOOST_REGEX_V5_PERL_MATCHER_NON_RECURSIVE_HPP
  21 #define BOOST_REGEX_V5_PERL_MATCHER_NON_RECURSIVE_HPP
  22
  23 #include <boost/regex/v5/mem_block_cache.hpp>
  24
  25 #ifdef BOOST_REGEX_MSVC
  26 #  pragma warning(push)
  27 #  pragma warning(disable: 4706 4459)
  28 #if BOOST_REGEX_MSVC < 1910
  29 #pragma warning(disable:4800)
  30 #endif
  31 #endif
  32
  33 namespace boost{
  34 namespace BOOST_REGEX_DETAIL_NS{
  35
  36 template <class T>
  37 inline void inplace_destroy(T* p)
  38 {
  39    (void)p;  // warning suppression
  40    p->~T();
  41 }
  42
  43 struct saved_state
  44 {
  45    union{
  46       unsigned int state_id;
  47       // this padding ensures correct alignment on 64-bit platforms:
  48       std::size_t padding1;
  49       std::ptrdiff_t padding2;
  50       void* padding3;
  51    };
  52    saved_state(unsigned i) : state_id(i) {}
  53 };
  54
  55 template <class BidiIterator>
  56 struct saved_matched_paren : public saved_state
  57 {
  58    int index;
  59    sub_match<BidiIterator> sub;
  60    saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){}
  61 };
  62
  63 template <class BidiIterator>
  64 struct saved_position : public saved_state
  65 {
  66    const re_syntax_base* pstate;
  67    BidiIterator position;
  68    saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){}
  69 };
  70
  71 template <class BidiIterator>
  72 struct saved_assertion : public saved_position<BidiIterator>
  73 {
  74    bool positive;
  75    saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
  76       : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){}
  77 };
  78
  79 template <class BidiIterator>
  80 struct saved_repeater : public saved_state
  81 {
  82    repeater_count<BidiIterator> count;
  83    saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start, int current_recursion_id)
  84       : saved_state(saved_state_repeater_count), count(i, s, start, current_recursion_id){}
  85 };
  86
  87 struct saved_extra_block : public saved_state
  88 {
  89    saved_state *base, *end;
  90    saved_extra_block(saved_state* b, saved_state* e)
  91       : saved_state(saved_state_extra_block), base(b), end(e) {}
  92 };
  93
  94 struct save_state_init
  95 {
  96    saved_state** stack;
  97    save_state_init(saved_state** base, saved_state** end)
  98       : stack(base)
  99    {
 100       *base = static_cast<saved_state*>(get_mem_block());
 101       *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
 102       --(*end);
 103       (void) new (*end)saved_state(0);
 104       BOOST_REGEX_ASSERT(*end > *base);
 105    }
 106    ~save_state_init()
 107    {
 108       put_mem_block(*stack);
 109       *stack = 0;
 110    }
 111 };
 112
 113 template <class BidiIterator>
 114 struct saved_single_repeat : public saved_state
 115 {
 116    std::size_t count;
 117    const re_repeat* rep;
 118    BidiIterator last_position;
 119    saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
 120       : saved_state(arg_id), count(c), rep(r), last_position(lp){}
 121 };
 122
 123 template <class Results>
 124 struct saved_recursion : public saved_state
 125 {
 126    saved_recursion(int idx, const re_syntax_base* p, Results* pr, Results* pr2)
 127       : saved_state(14), recursion_id(idx), preturn_address(p), internal_results(*pr), prior_results(*pr2) {}
 128    int recursion_id;
 129    const re_syntax_base* preturn_address;
 130    Results internal_results, prior_results;
 131 };
 132
 133 struct saved_change_case : public saved_state
 134 {
 135    bool icase;
 136    saved_change_case(bool c) : saved_state(18), icase(c) {}
 137 };
 138
 139 struct incrementer
 140 {
 141    incrementer(unsigned* pu) : m_pu(pu) { ++*m_pu; }
 142    ~incrementer() { --*m_pu; }
 143    bool operator > (unsigned i) { return *m_pu > i; }
 144 private:
 145    unsigned* m_pu;
 146 };
 147
 148 template <class BidiIterator, class Allocator, class traits>
 149 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
 150 {
 151    static matcher_proc_type const s_match_vtable[34] =
 152    {
 153       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
 154       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
 155       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
 156       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
 157       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
 158       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
 159       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
 160       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
 161       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
 162       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
 163       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
 164       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
 165       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
 166       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
 167       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
 168       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
 169       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
 170       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
 171       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
 172       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
 173       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
 174       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
 175       // Although this next line *should* be evaluated at compile time, in practice
 176       // some compilers (VC++) emit run-time initialisation which breaks thread
 177       // safety, so use a dispatch function instead:
 178       //(::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),
 179       &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
 180       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
 181       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
 182       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
 183       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
 184       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
 185       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
 186       &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
 187       &perl_matcher<BidiIterator, Allocator, traits>::match_fail,
 188       &perl_matcher<BidiIterator, Allocator, traits>::match_accept,
 189       &perl_matcher<BidiIterator, Allocator, traits>::match_commit,
 190       &perl_matcher<BidiIterator, Allocator, traits>::match_then,
 191    };
 192    incrementer inc(&m_recursions);
 193    if(inc > 80)
 194       raise_error(traits_inst, regex_constants::error_complexity);
 195    push_recursion_stopper();
 196    do{
 197       while(pstate)
 198       {
 199          matcher_proc_type proc = s_match_vtable[pstate->type];
 200          ++state_count;
 201          if(!(this->*proc)())
 202          {
 203             if(state_count > max_state_count)
 204                raise_error(traits_inst, regex_constants::error_complexity);
 205             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 206                m_has_partial_match = true;
 207             bool successful_unwind = unwind(false);
 208             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 209                m_has_partial_match = true;
 210             if(!successful_unwind)
 211                return m_recursive_result;
 212          }
 213       }
 214    }while(unwind(true));
 215    return m_recursive_result;
 216 }
 217
 218 template <class BidiIterator, class Allocator, class traits>
 219 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
 220 {
 221    if(used_block_count)
 222    {
 223       --used_block_count;
 224       saved_state* stack_base;
 225       saved_state* backup_state;
 226       stack_base = static_cast<saved_state*>(get_mem_block());
 227       backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
 228       saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
 229       --block;
 230       (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
 231       m_stack_base = stack_base;
 232       m_backup_state = block;
 233    }
 234    else
 235       raise_error(traits_inst, regex_constants::error_stack);
 236 }
 237
 238 template <class BidiIterator, class Allocator, class traits>
 239 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
 240 {
 241    //BOOST_REGEX_ASSERT(index);
 242    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 243    --pmp;
 244    if(pmp < m_stack_base)
 245    {
 246       extend_stack();
 247       pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 248       --pmp;
 249    }
 250    (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
 251    m_backup_state = pmp;
 252 }
 253
 254 template <class BidiIterator, class Allocator, class traits>
 255 inline void perl_matcher<BidiIterator, Allocator, traits>::push_case_change(bool c)
 256 {
 257    //BOOST_REGEX_ASSERT(index);
 258    saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
 259    --pmp;
 260    if(pmp < m_stack_base)
 261    {
 262       extend_stack();
 263       pmp = static_cast<saved_change_case*>(m_backup_state);
 264       --pmp;
 265    }
 266    (void) new (pmp)saved_change_case(c);
 267    m_backup_state = pmp;
 268 }
 269
 270 template <class BidiIterator, class Allocator, class traits>
 271 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
 272 {
 273    saved_state* pmp = m_backup_state;
 274    --pmp;
 275    if(pmp < m_stack_base)
 276    {
 277       extend_stack();
 278       pmp = m_backup_state;
 279       --pmp;
 280    }
 281    (void) new (pmp)saved_state(saved_type_recurse);
 282    m_backup_state = pmp;
 283 }
 284
 285 template <class BidiIterator, class Allocator, class traits>
 286 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
 287 {
 288    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 289    --pmp;
 290    if(pmp < m_stack_base)
 291    {
 292       extend_stack();
 293       pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 294       --pmp;
 295    }
 296    (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
 297    m_backup_state = pmp;
 298 }
 299
 300 template <class BidiIterator, class Allocator, class traits>
 301 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
 302 {
 303    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 304    --pmp;
 305    if(pmp < m_stack_base)
 306    {
 307       extend_stack();
 308       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 309       --pmp;
 310    }
 311    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
 312    m_backup_state = pmp;
 313 }
 314
 315 template <class BidiIterator, class Allocator, class traits>
 316 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
 317 {
 318    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 319    --pmp;
 320    if(pmp < m_stack_base)
 321    {
 322       extend_stack();
 323       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 324       --pmp;
 325    }
 326    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
 327    m_backup_state = pmp;
 328 }
 329
 330 template <class BidiIterator, class Allocator, class traits>
 331 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
 332 {
 333    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 334    --pmp;
 335    if(pmp < m_stack_base)
 336    {
 337       extend_stack();
 338       pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 339       --pmp;
 340    }
 341    (void) new (pmp)saved_repeater<BidiIterator>(i, s, position, this->recursion_stack.empty() ? (INT_MIN + 3) : this->recursion_stack.back().idx);
 342    m_backup_state = pmp;
 343 }
 344
 345 template <class BidiIterator, class Allocator, class traits>
 346 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
 347 {
 348    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 349    --pmp;
 350    if(pmp < m_stack_base)
 351    {
 352       extend_stack();
 353       pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 354       --pmp;
 355    }
 356    (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
 357    m_backup_state = pmp;
 358 }
 359
 360 template <class BidiIterator, class Allocator, class traits>
 361 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int idx, const re_syntax_base* p, results_type* presults, results_type* presults2)
 362 {
 363    saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
 364    --pmp;
 365    if(pmp < m_stack_base)
 366    {
 367       extend_stack();
 368       pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
 369       --pmp;
 370    }
 371    (void) new (pmp)saved_recursion<results_type>(idx, p, presults, presults2);
 372    m_backup_state = pmp;
 373 }
 374
 375 template <class BidiIterator, class Allocator, class traits>
 376 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
 377 {
 378    // change our case sensitivity:
 379    push_case_change(this->icase);
 380    this->icase = static_cast<const re_case*>(pstate)->icase;
 381    pstate = pstate->next.p;
 382    return true;
 383 }
 384
 385 template <class BidiIterator, class Allocator, class traits>
 386 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
 387 {
 388    int index = static_cast<const re_brace*>(pstate)->index;
 389    icase = static_cast<const re_brace*>(pstate)->icase;
 390    switch(index)
 391    {
 392    case 0:
 393       pstate = pstate->next.p;
 394       break;
 395    case -1:
 396    case -2:
 397       {
 398          // forward lookahead assert:
 399          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 400          pstate = pstate->next.p->next.p;
 401          push_assertion(next_pstate, index == -1);
 402          break;
 403       }
 404    case -3:
 405       {
 406          // independent sub-expression, currently this is always recursive:
 407          bool old_independent = m_independent;
 408          m_independent = true;
 409          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 410          pstate = pstate->next.p->next.p;
 411          bool r = false;
 412 #if !defined(BOOST_NO_EXCEPTIONS)
 413       try{
 414 #endif
 415          r = match_all_states();
 416          if(!r && !m_independent)
 417          {
 418             // Must be unwinding from a COMMIT/SKIP/PRUNE and the independent
 419             // sub failed, need to unwind everything else:
 420             while (m_backup_state->state_id)
 421                unwind(false);
 422             return false;
 423          }
 424 #if !defined(BOOST_NO_EXCEPTIONS)
 425       }
 426       catch(...)
 427       {
 428          pstate = next_pstate;
 429          // unwind all pushed states, apart from anything else this
 430          // ensures that all the states are correctly destructed
 431          // not just the memory freed.
 432          while(unwind(true)) {}
 433          throw;
 434       }
 435 #endif
 436       pstate = next_pstate;
 437       m_independent = old_independent;
 438 #ifdef BOOST_REGEX_MATCH_EXTRA
 439          if(r && (m_match_flags & match_extra))
 440          {
 441             //
 442             // our captures have been stored in *m_presult
 443             // we need to unpack them, and insert them
 444             // back in the right order when we unwind the stack:
 445             //
 446             match_results<BidiIterator, Allocator> temp_match(*m_presult);
 447             unsigned i;
 448             for(i = 0; i < temp_match.size(); ++i)
 449                (*m_presult)[i].get_captures().clear();
 450             // match everything else:
 451 #if !defined(BOOST_NO_EXCEPTIONS)
 452             try{
 453 #endif
 454                r = match_all_states();
 455 #if !defined(BOOST_NO_EXCEPTIONS)
 456             }
 457             catch(...)
 458             {
 459                pstate = next_pstate;
 460                // unwind all pushed states, apart from anything else this
 461                // ensures that all the states are correctly destructed
 462                // not just the memory freed.
 463                while(unwind(true)) {}
 464                throw;
 465             }
 466 #endif
 467          // now place the stored captures back:
 468             for(i = 0; i < temp_match.size(); ++i)
 469             {
 470                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
 471                seq& s1 = (*m_presult)[i].get_captures();
 472                const seq& s2 = temp_match[i].captures();
 473                s1.insert(
 474                   s1.end(),
 475                   s2.begin(),
 476                   s2.end());
 477             }
 478          }
 479 #endif
 480          return r;
 481       }
 482    case -4:
 483       {
 484       // conditional expression:
 485       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
 486       BOOST_REGEX_ASSERT(alt->type == syntax_element_alt);
 487       pstate = alt->next.p;
 488       if(pstate->type == syntax_element_assert_backref)
 489       {
 490          if(!match_assert_backref())
 491             pstate = alt->alt.p;
 492          break;
 493       }
 494       else
 495       {
 496          // zero width assertion, have to match this recursively:
 497          BOOST_REGEX_ASSERT(pstate->type == syntax_element_startmark);
 498          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
 499          BidiIterator saved_position = position;
 500          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 501          pstate = pstate->next.p->next.p;
 502 #if !defined(BOOST_NO_EXCEPTIONS)
 503          try{
 504 #endif
 505             bool r = match_all_states();
 506             position = saved_position;
 507             if(negated)
 508                r = !r;
 509             if(r)
 510                pstate = next_pstate;
 511             else
 512                pstate = alt->alt.p;
 513 #if !defined(BOOST_NO_EXCEPTIONS)
 514          }
 515          catch(...)
 516          {
 517             pstate = next_pstate;
 518             // unwind all pushed states, apart from anything else this
 519             // ensures that all the states are correctly destructed
 520             // not just the memory freed.
 521             while(unwind(true)){}
 522             throw;
 523          }
 524 #endif
 525          break;
 526       }
 527       }
 528    case -5:
 529       {
 530          push_matched_paren(0, (*m_presult)[0]);
 531          m_presult->set_first(position, 0, true);
 532          pstate = pstate->next.p;
 533          break;
 534       }
 535    default:
 536    {
 537       BOOST_REGEX_ASSERT(index > 0);
 538       if((m_match_flags & match_nosubs) == 0)
 539       {
 540          push_matched_paren(index, (*m_presult)[index]);
 541          m_presult->set_first(position, index);
 542       }
 543       pstate = pstate->next.p;
 544       break;
 545    }
 546    }
 547    return true;
 548 }
 549
 550 template <class BidiIterator, class Allocator, class traits>
 551 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
 552 {
 553    bool take_first, take_second;
 554    const re_alt* jmp = static_cast<const re_alt*>(pstate);
 555
 556    // find out which of these two alternatives we need to take:
 557    if(position == last)
 558    {
 559       take_first = jmp->can_be_null & mask_take;
 560       take_second = jmp->can_be_null & mask_skip;
 561    }
 562    else
 563    {
 564       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
 565       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
 566   }
 567
 568    if(take_first)
 569    {
 570       // we can take the first alternative,
 571       // see if we need to push next alternative:
 572       if(take_second)
 573       {
 574          push_alt(jmp->alt.p);
 575       }
 576       pstate = pstate->next.p;
 577       return true;
 578    }
 579    if(take_second)
 580    {
 581       pstate = jmp->alt.p;
 582       return true;
 583    }
 584    return false;  // neither option is possible
 585 }
 586
 587 template <class BidiIterator, class Allocator, class traits>
 588 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
 589 {
 590 #ifdef BOOST_REGEX_MSVC
 591 #pragma warning(push)
 592 #pragma warning(disable:4127 4244)
 593 #endif
 594 #ifdef BOOST_BORLANDC
 595 #pragma option push -w-8008 -w-8066 -w-8004
 596 #endif
 597    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 598
 599    // find out which of these two alternatives we need to take:
 600    bool take_first, take_second;
 601    if(position == last)
 602    {
 603       take_first = rep->can_be_null & mask_take;
 604       take_second = rep->can_be_null & mask_skip;
 605    }
 606    else
 607    {
 608       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
 609       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
 610    }
 611
 612    if((m_backup_state->state_id != saved_state_repeater_count)
 613       || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
 614       || (next_count->get_id() != rep->state_id))
 615    {
 616       // we're moving to a different repeat from the last
 617       // one, so set up a counter object:
 618       push_repeater_count(rep->state_id, &next_count);
 619    }
 620    //
 621    // If we've had at least one repeat already, and the last one
 622    // matched the NULL string then set the repeat count to
 623    // maximum:
 624    //
 625    next_count->check_null_repeat(position, rep->max);
 626
 627    if(next_count->get_count() < rep->min)
 628    {
 629       // we must take the repeat:
 630       if(take_first)
 631       {
 632          // increase the counter:
 633          ++(*next_count);
 634          pstate = rep->next.p;
 635          return true;
 636       }
 637       return false;
 638    }
 639
 640    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 641    if(greedy)
 642    {
 643       // try and take the repeat if we can:
 644       if((next_count->get_count() < rep->max) && take_first)
 645       {
 646          if(take_second)
 647          {
 648             // store position in case we fail:
 649             push_alt(rep->alt.p);
 650          }
 651          // increase the counter:
 652          ++(*next_count);
 653          pstate = rep->next.p;
 654          return true;
 655       }
 656       else if(take_second)
 657       {
 658          pstate = rep->alt.p;
 659          return true;
 660       }
 661       return false; // can't take anything, fail...
 662    }
 663    else // non-greedy
 664    {
 665       // try and skip the repeat if we can:
 666       if(take_second)
 667       {
 668          if((next_count->get_count() < rep->max) && take_first)
 669          {
 670             // store position in case we fail:
 671             push_non_greedy_repeat(rep->next.p);
 672          }
 673          pstate = rep->alt.p;
 674          return true;
 675       }
 676       if((next_count->get_count() < rep->max) && take_first)
 677       {
 678          // increase the counter:
 679          ++(*next_count);
 680          pstate = rep->next.p;
 681          return true;
 682       }
 683    }
 684    return false;
 685 #ifdef BOOST_BORLANDC
 686 #pragma option pop
 687 #endif
 688 #ifdef BOOST_REGEX_MSVC
 689 #pragma warning(pop)
 690 #endif
 691 }
 692
 693 template <class BidiIterator, class Allocator, class traits>
 694 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 695 {
 696    std::size_t count = 0;
 697    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 698    re_syntax_base* psingle = rep->next.p;
 699    // match compulsory repeats first:
 700    while(count < rep->min)
 701    {
 702       pstate = psingle;
 703       if(!match_wild())
 704          return false;
 705       ++count;
 706    }
 707    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 708    if(greedy)
 709    {
 710       // repeat for as long as we can:
 711       while(count < rep->max)
 712       {
 713          pstate = psingle;
 714          if(!match_wild())
 715             break;
 716          ++count;
 717       }
 718       // remember where we got to if this is a leading repeat:
 719       if((rep->leading) && (count < rep->max))
 720          restart = position;
 721       // push backtrack info if available:
 722       if(count - rep->min)
 723          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 724       // jump to next state:
 725       pstate = rep->alt.p;
 726       return true;
 727    }
 728    else
 729    {
 730       // non-greedy, push state and return true if we can skip:
 731       if(count < rep->max)
 732          push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
 733       pstate = rep->alt.p;
 734       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 735    }
 736 }
 737
 738 template <class BidiIterator, class Allocator, class traits>
 739 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 740 {
 741    if(m_match_flags & match_not_dot_null)
 742       return match_dot_repeat_slow();
 743    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 744       return match_dot_repeat_slow();
 745
 746    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 747    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 748    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));
 749    if(rep->min > count)
 750    {
 751       position = last;
 752       return false;  // not enough text left to match
 753    }
 754    std::advance(position, count);
 755
 756    if(greedy)
 757    {
 758       if((rep->leading) && (count < rep->max))
 759          restart = position;
 760       // push backtrack info if available:
 761       if(count - rep->min)
 762          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 763       // jump to next state:
 764       pstate = rep->alt.p;
 765       return true;
 766    }
 767    else
 768    {
 769       // non-greedy, push state and return true if we can skip:
 770       if(count < rep->max)
 771          push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
 772       pstate = rep->alt.p;
 773       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 774    }
 775 }
 776
 777 template <class BidiIterator, class Allocator, class traits>
 778 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 779 {
 780 #ifdef BOOST_REGEX_MSVC
 781 #pragma warning(push)
 782 #pragma warning(disable:4127)
 783 #endif
 784 #ifdef BOOST_BORLANDC
 785 #pragma option push -w-8008 -w-8066 -w-8004
 786 #endif
 787    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 788    BOOST_REGEX_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 789    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 790    std::size_t count = 0;
 791    //
 792    // start by working out how much we can skip:
 793    //
 794    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 795    std::size_t desired = greedy ? rep->max : rep->min;
 796    if(::boost::is_random_access_iterator<BidiIterator>::value)
 797    {
 798       BidiIterator end = position;
 799       // Move end forward by "desired", preferably without using distance or advance if we can
 800       // as these can be slow for some iterator types.
 801       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
 802       if(desired >= len)
 803          end = last;
 804       else
 805          std::advance(end, desired);
 806       BidiIterator origin(position);
 807       while((position != end) && (traits_inst.translate(*position, icase) == what))
 808       {
 809          ++position;
 810       }
 811       count = (unsigned)std::distance(origin, position);
 812    }
 813    else
 814    {
 815       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 816       {
 817          ++position;
 818          ++count;
 819       }
 820    }
 821
 822    if(count < rep->min)
 823       return false;
 824
 825    if(greedy)
 826    {
 827       if((rep->leading) && (count < rep->max))
 828          restart = position;
 829       // push backtrack info if available:
 830       if(count - rep->min)
 831          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 832       // jump to next state:
 833       pstate = rep->alt.p;
 834       return true;
 835    }
 836    else
 837    {
 838       // non-greedy, push state and return true if we can skip:
 839       if(count < rep->max)
 840          push_single_repeat(count, rep, position, saved_state_rep_char);
 841       pstate = rep->alt.p;
 842       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 843    }
 844 #ifdef BOOST_BORLANDC
 845 #pragma option pop
 846 #endif
 847 #ifdef BOOST_REGEX_MSVC
 848 #pragma warning(pop)
 849 #endif
 850 }
 851
 852 template <class BidiIterator, class Allocator, class traits>
 853 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 854 {
 855 #ifdef BOOST_REGEX_MSVC
 856 #pragma warning(push)
 857 #pragma warning(disable:4127)
 858 #endif
 859 #ifdef BOOST_BORLANDC
 860 #pragma option push -w-8008 -w-8066 -w-8004
 861 #endif
 862    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 863    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 864    std::size_t count = 0;
 865    //
 866    // start by working out how much we can skip:
 867    //
 868    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 869    std::size_t desired = greedy ? rep->max : rep->min;
 870    if(::boost::is_random_access_iterator<BidiIterator>::value)
 871    {
 872       BidiIterator end = position;
 873       // Move end forward by "desired", preferably without using distance or advance if we can
 874       // as these can be slow for some iterator types.
 875       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
 876       if(desired >= len)
 877          end = last;
 878       else
 879          std::advance(end, desired);
 880       BidiIterator origin(position);
 881       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 882       {
 883          ++position;
 884       }
 885       count = (unsigned)std::distance(origin, position);
 886    }
 887    else
 888    {
 889       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 890       {
 891          ++position;
 892          ++count;
 893       }
 894    }
 895
 896    if(count < rep->min)
 897       return false;
 898
 899    if(greedy)
 900    {
 901       if((rep->leading) && (count < rep->max))
 902          restart = position;
 903       // push backtrack info if available:
 904       if(count - rep->min)
 905          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 906       // jump to next state:
 907       pstate = rep->alt.p;
 908       return true;
 909    }
 910    else
 911    {
 912       // non-greedy, push state and return true if we can skip:
 913       if(count < rep->max)
 914          push_single_repeat(count, rep, position, saved_state_rep_short_set);
 915       pstate = rep->alt.p;
 916       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 917    }
 918 #ifdef BOOST_BORLANDC
 919 #pragma option pop
 920 #endif
 921 #ifdef BOOST_REGEX_MSVC
 922 #pragma warning(pop)
 923 #endif
 924 }
 925
 926 template <class BidiIterator, class Allocator, class traits>
 927 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 928 {
 929 #ifdef BOOST_REGEX_MSVC
 930 #pragma warning(push)
 931 #pragma warning(disable:4127)
 932 #endif
 933 #ifdef BOOST_BORLANDC
 934 #pragma option push -w-8008 -w-8066 -w-8004
 935 #endif
 936    typedef typename traits::char_class_type m_type;
 937    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 938    const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate->next.p);
 939    std::size_t count = 0;
 940    //
 941    // start by working out how much we can skip:
 942    //
 943    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 944    std::size_t desired = greedy ? rep->max : rep->min;
 945    if(::boost::is_random_access_iterator<BidiIterator>::value)
 946    {
 947       BidiIterator end = position;
 948       // Move end forward by "desired", preferably without using distance or advance if we can
 949       // as these can be slow for some iterator types.
 950       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
 951       if(desired >= len)
 952          end = last;
 953       else
 954          std::advance(end, desired);
 955       BidiIterator origin(position);
 956       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 957       {
 958          ++position;
 959       }
 960       count = (unsigned)std::distance(origin, position);
 961    }
 962    else
 963    {
 964       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 965       {
 966          ++position;
 967          ++count;
 968       }
 969    }
 970
 971    if(count < rep->min)
 972       return false;
 973
 974    if(greedy)
 975    {
 976       if((rep->leading) && (count < rep->max))
 977          restart = position;
 978       // push backtrack info if available:
 979       if(count - rep->min)
 980          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 981       // jump to next state:
 982       pstate = rep->alt.p;
 983       return true;
 984    }
 985    else
 986    {
 987       // non-greedy, push state and return true if we can skip:
 988       if(count < rep->max)
 989          push_single_repeat(count, rep, position, saved_state_rep_long_set);
 990       pstate = rep->alt.p;
 991       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 992    }
 993 #ifdef BOOST_BORLANDC
 994 #pragma option pop
 995 #endif
 996 #ifdef BOOST_REGEX_MSVC
 997 #pragma warning(pop)
 998 #endif
 999 }
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