boost/boost/regex/v4/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_V4_PERL_MATCHER_NON_RECURSIVE_HPP
  21 #define BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP
  22
  23 #include <new>
  24
  25 #ifdef BOOST_MSVC
  26 #pragma warning(push)
  27 #pragma warning(disable: 4103)
  28 #endif
  29 #ifdef BOOST_HAS_ABI_HEADERS
  30 #  include BOOST_ABI_PREFIX
  31 #endif
  32 #ifdef BOOST_MSVC
  33 #pragma warning(pop)
  34 #endif
  35 #ifdef BOOST_MSVC
  36 #  pragma warning(push)
  37 #  pragma warning(disable: 4800)
  38 #endif
  39
  40 namespace boost{
  41 namespace re_detail{
  42
  43 template <class T>
  44 inline void inplace_destroy(T* p)
  45 {
  46    (void)p;  // warning suppression
  47    p->~T();
  48 }
  49
  50 struct saved_state
  51 {
  52    union{
  53       unsigned int state_id;
  54       // this padding ensures correct alignment on 64-bit platforms:
  55       std::size_t padding1;
  56       std::ptrdiff_t padding2;
  57       void* padding3;
  58    };
  59    saved_state(unsigned i) : state_id(i) {}
  60 };
  61
  62 template <class BidiIterator>
  63 struct saved_matched_paren : public saved_state
  64 {
  65    int index;
  66    sub_match<BidiIterator> sub;
  67    saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};
  68 };
  69
  70 template <class BidiIterator>
  71 struct saved_position : public saved_state
  72 {
  73    const re_syntax_base* pstate;
  74    BidiIterator position;
  75    saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};
  76 };
  77
  78 template <class BidiIterator>
  79 struct saved_assertion : public saved_position<BidiIterator>
  80 {
  81    bool positive;
  82    saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
  83       : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};
  84 };
  85
  86 template <class BidiIterator>
  87 struct saved_repeater : public saved_state
  88 {
  89    repeater_count<BidiIterator> count;
  90    saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start)
  91       : saved_state(saved_state_repeater_count), count(i,s,start){}
  92 };
  93
  94 struct saved_extra_block : public saved_state
  95 {
  96    saved_state *base, *end;
  97    saved_extra_block(saved_state* b, saved_state* e)
  98       : saved_state(saved_state_extra_block), base(b), end(e) {}
  99 };
 100
 101 struct save_state_init
 102 {
 103    saved_state** stack;
 104    save_state_init(saved_state** base, saved_state** end)
 105       : stack(base)
 106    {
 107       *base = static_cast<saved_state*>(get_mem_block());
 108       *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);
 109       --(*end);
 110       (void) new (*end)saved_state(0);
 111       BOOST_ASSERT(*end > *base);
 112    }
 113    ~save_state_init()
 114    {
 115       put_mem_block(*stack);
 116       *stack = 0;
 117    }
 118 };
 119
 120 template <class BidiIterator>
 121 struct saved_single_repeat : public saved_state
 122 {
 123    std::size_t count;
 124    const re_repeat* rep;
 125    BidiIterator last_position;
 126    saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
 127       : saved_state(arg_id), count(c), rep(r), last_position(lp){}
 128 };
 129
 130 template <class BidiIterator, class Allocator, class traits>
 131 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
 132 {
 133    static matcher_proc_type const s_match_vtable[29] =
 134    {
 135       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
 136       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
 137       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
 138       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
 139       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
 140       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
 141       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
 142       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
 143       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
 144       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
 145       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
 146       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
 147       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
 148       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
 149       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
 150       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
 151       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
 152       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
 153       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
 154       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
 155       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
 156       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
 157       (::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),
 158       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
 159       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
 160       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
 161       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
 162       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
 163       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
 164    };
 165
 166    push_recursion_stopper();
 167    do{
 168       while(pstate)
 169       {
 170          matcher_proc_type proc = s_match_vtable[pstate->type];
 171          ++state_count;
 172          if(!(this->*proc)())
 173          {
 174             if(state_count > max_state_count)
 175                raise_error(traits_inst, regex_constants::error_space);
 176             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 177                m_has_partial_match = true;
 178             bool successful_unwind = unwind(false);
 179             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 180                m_has_partial_match = true;
 181             if(false == successful_unwind)
 182                return m_recursive_result;
 183          }
 184       }
 185    }while(unwind(true));
 186    return m_recursive_result;
 187 }
 188
 189 template <class BidiIterator, class Allocator, class traits>
 190 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
 191 {
 192    if(used_block_count)
 193    {
 194       --used_block_count;
 195       saved_state* stack_base;
 196       saved_state* backup_state;
 197       stack_base = static_cast<saved_state*>(get_mem_block());
 198       backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
 199       saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
 200       --block;
 201       (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
 202       m_stack_base = stack_base;
 203       m_backup_state = block;
 204    }
 205    else
 206       raise_error(traits_inst, regex_constants::error_size);
 207 }
 208
 209 template <class BidiIterator, class Allocator, class traits>
 210 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
 211 {
 212    BOOST_ASSERT(index);
 213    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 214    --pmp;
 215    if(pmp < m_stack_base)
 216    {
 217       extend_stack();
 218       pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 219       --pmp;
 220    }
 221    (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
 222    m_backup_state = pmp;
 223 }
 224
 225 template <class BidiIterator, class Allocator, class traits>
 226 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
 227 {
 228    saved_state* pmp = m_backup_state;
 229    --pmp;
 230    if(pmp < m_stack_base)
 231    {
 232       extend_stack();
 233       pmp = m_backup_state;
 234       --pmp;
 235    }
 236    (void) new (pmp)saved_state(saved_type_recurse);
 237    m_backup_state = pmp;
 238 }
 239
 240 template <class BidiIterator, class Allocator, class traits>
 241 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
 242 {
 243    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 244    --pmp;
 245    if(pmp < m_stack_base)
 246    {
 247       extend_stack();
 248       pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 249       --pmp;
 250    }
 251    (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
 252    m_backup_state = pmp;
 253 }
 254
 255 template <class BidiIterator, class Allocator, class traits>
 256 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
 257 {
 258    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 259    --pmp;
 260    if(pmp < m_stack_base)
 261    {
 262       extend_stack();
 263       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 264       --pmp;
 265    }
 266    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
 267    m_backup_state = pmp;
 268 }
 269
 270 template <class BidiIterator, class Allocator, class traits>
 271 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
 272 {
 273    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 274    --pmp;
 275    if(pmp < m_stack_base)
 276    {
 277       extend_stack();
 278       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 279       --pmp;
 280    }
 281    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
 282    m_backup_state = pmp;
 283 }
 284
 285 template <class BidiIterator, class Allocator, class traits>
 286 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
 287 {
 288    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 289    --pmp;
 290    if(pmp < m_stack_base)
 291    {
 292       extend_stack();
 293       pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 294       --pmp;
 295    }
 296    (void) new (pmp)saved_repeater<BidiIterator>(i, s, 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_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
 302 {
 303    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 304    --pmp;
 305    if(pmp < m_stack_base)
 306    {
 307       extend_stack();
 308       pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 309       --pmp;
 310    }
 311    (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
 312    m_backup_state = pmp;
 313 }
 314
 315 template <class BidiIterator, class Allocator, class traits>
 316 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
 317 {
 318    int index = static_cast<const re_brace*>(pstate)->index;
 319    switch(index)
 320    {
 321    case 0:
 322       pstate = pstate->next.p;
 323       break;
 324    case -1:
 325    case -2:
 326       {
 327          // forward lookahead assert:
 328          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 329          pstate = pstate->next.p->next.p;
 330          push_assertion(next_pstate, index == -1);
 331          break;
 332       }
 333    case -3:
 334       {
 335          // independent sub-expression, currently this is always recursive:
 336          bool old_independent = m_independent;
 337          m_independent = true;
 338          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 339          pstate = pstate->next.p->next.p;
 340          bool r = match_all_states();
 341          pstate = next_pstate;
 342          m_independent = old_independent;
 343 #ifdef BOOST_REGEX_MATCH_EXTRA
 344          if(r && (m_match_flags & match_extra))
 345          {
 346             //
 347             // our captures have been stored in *m_presult
 348             // we need to unpack them, and insert them
 349             // back in the right order when we unwind the stack:
 350             //
 351             match_results<BidiIterator, Allocator> temp_match(*m_presult);
 352             unsigned i;
 353             for(i = 0; i < temp_match.size(); ++i)
 354                (*m_presult)[i].get_captures().clear();
 355             // match everything else:
 356             r = match_all_states();
 357             // now place the stored captures back:
 358             for(i = 0; i < temp_match.size(); ++i)
 359             {
 360                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
 361                seq& s1 = (*m_presult)[i].get_captures();
 362                const seq& s2 = temp_match[i].captures();
 363                s1.insert(
 364                   s1.end(),
 365                   s2.begin(),
 366                   s2.end());
 367             }
 368          }
 369 #endif
 370          return r;
 371       }
 372    case -4:
 373       {
 374       // conditional expression:
 375       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
 376       BOOST_ASSERT(alt->type == syntax_element_alt);
 377       pstate = alt->next.p;
 378       if(pstate->type == syntax_element_assert_backref)
 379       {
 380          if(!match_assert_backref())
 381             pstate = alt->alt.p;
 382          break;
 383       }
 384       else
 385       {
 386          // zero width assertion, have to match this recursively:
 387          BOOST_ASSERT(pstate->type == syntax_element_startmark);
 388          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
 389          BidiIterator saved_position = position;
 390          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 391          pstate = pstate->next.p->next.p;
 392          bool r = match_all_states();
 393          position = saved_position;
 394          if(negated)
 395             r = !r;
 396          if(r)
 397             pstate = next_pstate;
 398          else
 399             pstate = alt->alt.p;
 400          break;
 401       }
 402       }
 403    default:
 404    {
 405       BOOST_ASSERT(index > 0);
 406       if((m_match_flags & match_nosubs) == 0)
 407       {
 408          push_matched_paren(index, (*m_presult)[index]);
 409          m_presult->set_first(position, index);
 410       }
 411       pstate = pstate->next.p;
 412       break;
 413    }
 414    }
 415    return true;
 416 }
 417
 418 template <class BidiIterator, class Allocator, class traits>
 419 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
 420 {
 421    bool take_first, take_second;
 422    const re_alt* jmp = static_cast<const re_alt*>(pstate);
 423
 424    // find out which of these two alternatives we need to take:
 425    if(position == last)
 426    {
 427       take_first = jmp->can_be_null & mask_take;
 428       take_second = jmp->can_be_null & mask_skip;
 429    }
 430    else
 431    {
 432       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
 433       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
 434   }
 435
 436    if(take_first)
 437    {
 438       // we can take the first alternative,
 439       // see if we need to push next alternative:
 440       if(take_second)
 441       {
 442          push_alt(jmp->alt.p);
 443       }
 444       pstate = pstate->next.p;
 445       return true;
 446    }
 447    if(take_second)
 448    {
 449       pstate = jmp->alt.p;
 450       return true;
 451    }
 452    return false;  // neither option is possible
 453 }
 454
 455 template <class BidiIterator, class Allocator, class traits>
 456 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
 457 {
 458 #ifdef BOOST_MSVC
 459 #pragma warning(push)
 460 #pragma warning(disable:4127 4244)
 461 #endif
 462 #ifdef __BORLANDC__
 463 #pragma option push -w-8008 -w-8066 -w-8004
 464 #endif
 465    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 466
 467    // find out which of these two alternatives we need to take:
 468    bool take_first, take_second;
 469    if(position == last)
 470    {
 471       take_first = rep->can_be_null & mask_take;
 472       take_second = rep->can_be_null & mask_skip;
 473    }
 474    else
 475    {
 476       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
 477       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
 478    }
 479
 480    if((m_backup_state->state_id != saved_state_repeater_count)
 481       || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
 482       || (next_count->get_id() != rep->state_id))
 483    {
 484       // we're moving to a different repeat from the last
 485       // one, so set up a counter object:
 486       push_repeater_count(rep->state_id, &next_count);
 487    }
 488    //
 489    // If we've had at least one repeat already, and the last one
 490    // matched the NULL string then set the repeat count to
 491    // maximum:
 492    //
 493    next_count->check_null_repeat(position, rep->max);
 494
 495    if(next_count->get_count() < rep->min)
 496    {
 497       // we must take the repeat:
 498       if(take_first)
 499       {
 500          // increase the counter:
 501          ++(*next_count);
 502          pstate = rep->next.p;
 503          return true;
 504       }
 505       return false;
 506    }
 507
 508    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 509    if(greedy)
 510    {
 511       // try and take the repeat if we can:
 512       if((next_count->get_count() < rep->max) && take_first)
 513       {
 514          if(take_second)
 515          {
 516             // store position in case we fail:
 517             push_alt(rep->alt.p);
 518          }
 519          // increase the counter:
 520          ++(*next_count);
 521          pstate = rep->next.p;
 522          return true;
 523       }
 524       else if(take_second)
 525       {
 526          pstate = rep->alt.p;
 527          return true;
 528       }
 529       return false; // can't take anything, fail...
 530    }
 531    else // non-greedy
 532    {
 533       // try and skip the repeat if we can:
 534       if(take_second)
 535       {
 536          if((next_count->get_count() < rep->max) && take_first)
 537          {
 538             // store position in case we fail:
 539             push_non_greedy_repeat(rep->next.p);
 540          }
 541          pstate = rep->alt.p;
 542          return true;
 543       }
 544       if((next_count->get_count() < rep->max) && take_first)
 545       {
 546          // increase the counter:
 547          ++(*next_count);
 548          pstate = rep->next.p;
 549          return true;
 550       }
 551    }
 552    return false;
 553 #ifdef __BORLANDC__
 554 #pragma option pop
 555 #endif
 556 #ifdef BOOST_MSVC
 557 #pragma warning(pop)
 558 #endif
 559 }
 560
 561 template <class BidiIterator, class Allocator, class traits>
 562 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 563 {
 564    unsigned count = 0;
 565    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 566    re_syntax_base* psingle = rep->next.p;
 567    // match compulsary repeats first:
 568    while(count < rep->min)
 569    {
 570       pstate = psingle;
 571       if(!match_wild())
 572          return false;
 573       ++count;
 574    }
 575    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 576    if(greedy)
 577    {
 578       // repeat for as long as we can:
 579       while(count < rep->max)
 580       {
 581          pstate = psingle;
 582          if(!match_wild())
 583             break;
 584          ++count;
 585       }
 586       // remember where we got to if this is a leading repeat:
 587       if((rep->leading) && (count < rep->max))
 588          restart = position;
 589       // push backtrack info if available:
 590       if(count - rep->min)
 591          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 592       // jump to next state:
 593       pstate = rep->alt.p;
 594       return true;
 595    }
 596    else
 597    {
 598       // non-greedy, push state and return true if we can skip:
 599       if(count < rep->max)
 600          push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
 601       pstate = rep->alt.p;
 602       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 603    }
 604 }
 605
 606 template <class BidiIterator, class Allocator, class traits>
 607 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 608 {
 609    if(m_match_flags & match_not_dot_null)
 610       return match_dot_repeat_slow();
 611    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 612       return match_dot_repeat_slow();
 613
 614    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 615    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 616    unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
 617    if(rep->min > count)
 618    {
 619       position = last;
 620       return false;  // not enough text left to match
 621    }
 622    std::advance(position, count);
 623
 624    if(greedy)
 625    {
 626       if((rep->leading) && (count < rep->max))
 627          restart = position;
 628       // push backtrack info if available:
 629       if(count - rep->min)
 630          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 631       // jump to next state:
 632       pstate = rep->alt.p;
 633       return true;
 634    }
 635    else
 636    {
 637       // non-greedy, push state and return true if we can skip:
 638       if(count < rep->max)
 639          push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
 640       pstate = rep->alt.p;
 641       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 642    }
 643 }
 644
 645 template <class BidiIterator, class Allocator, class traits>
 646 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 647 {
 648 #ifdef BOOST_MSVC
 649 #pragma warning(push)
 650 #pragma warning(disable:4127)
 651 #endif
 652 #ifdef __BORLANDC__
 653 #pragma option push -w-8008 -w-8066 -w-8004
 654 #endif
 655    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 656    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 657    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 658    std::size_t count = 0;
 659    //
 660    // start by working out how much we can skip:
 661    //
 662    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 663    std::size_t desired = greedy ? rep->max : rep->min;
 664    if(::boost::is_random_access_iterator<BidiIterator>::value)
 665    {
 666       BidiIterator end = position;
 667       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 668       BidiIterator origin(position);
 669       while((position != end) && (traits_inst.translate(*position, icase) == what))
 670       {
 671          ++position;
 672       }
 673       count = (unsigned)::boost::re_detail::distance(origin, position);
 674    }
 675    else
 676    {
 677       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 678       {
 679          ++position;
 680          ++count;
 681       }
 682    }
 683
 684    if(count < rep->min)
 685       return false;
 686
 687    if(greedy)
 688    {
 689       if((rep->leading) && (count < rep->max))
 690          restart = position;
 691       // push backtrack info if available:
 692       if(count - rep->min)
 693          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 694       // jump to next state:
 695       pstate = rep->alt.p;
 696       return true;
 697    }
 698    else
 699    {
 700       // non-greedy, push state and return true if we can skip:
 701       if(count < rep->max)
 702          push_single_repeat(count, rep, position, saved_state_rep_char);
 703       pstate = rep->alt.p;
 704       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 705    }
 706 #ifdef __BORLANDC__
 707 #pragma option pop
 708 #endif
 709 #ifdef BOOST_MSVC
 710 #pragma warning(pop)
 711 #endif
 712 }
 713
 714 template <class BidiIterator, class Allocator, class traits>
 715 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 716 {
 717 #ifdef BOOST_MSVC
 718 #pragma warning(push)
 719 #pragma warning(disable:4127)
 720 #endif
 721 #ifdef __BORLANDC__
 722 #pragma option push -w-8008 -w-8066 -w-8004
 723 #endif
 724    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 725    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 726    std::size_t count = 0;
 727    //
 728    // start by working out how much we can skip:
 729    //
 730    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 731    std::size_t desired = greedy ? rep->max : rep->min;
 732    if(::boost::is_random_access_iterator<BidiIterator>::value)
 733    {
 734       BidiIterator end = position;
 735       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 736       BidiIterator origin(position);
 737       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 738       {
 739          ++position;
 740       }
 741       count = (unsigned)::boost::re_detail::distance(origin, position);
 742    }
 743    else
 744    {
 745       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 746       {
 747          ++position;
 748          ++count;
 749       }
 750    }
 751
 752    if(count < rep->min)
 753       return false;
 754
 755    if(greedy)
 756    {
 757       if((rep->leading) && (count < rep->max))
 758          restart = position;
 759       // push backtrack info if available:
 760       if(count - rep->min)
 761          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 762       // jump to next state:
 763       pstate = rep->alt.p;
 764       return true;
 765    }
 766    else
 767    {
 768       // non-greedy, push state and return true if we can skip:
 769       if(count < rep->max)
 770          push_single_repeat(count, rep, position, saved_state_rep_short_set);
 771       pstate = rep->alt.p;
 772       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 773    }
 774 #ifdef __BORLANDC__
 775 #pragma option pop
 776 #endif
 777 #ifdef BOOST_MSVC
 778 #pragma warning(pop)
 779 #endif
 780 }
 781
 782 template <class BidiIterator, class Allocator, class traits>
 783 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 784 {
 785 #ifdef BOOST_MSVC
 786 #pragma warning(push)
 787 #pragma warning(disable:4127)
 788 #endif
 789 #ifdef __BORLANDC__
 790 #pragma option push -w-8008 -w-8066 -w-8004
 791 #endif
 792    typedef typename traits::char_class_type mask_type;
 793    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 794    const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate->next.p);
 795    std::size_t count = 0;
 796    //
 797    // start by working out how much we can skip:
 798    //
 799    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 800    std::size_t desired = greedy ? rep->max : rep->min;
 801    if(::boost::is_random_access_iterator<BidiIterator>::value)
 802    {
 803       BidiIterator end = position;
 804       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 805       BidiIterator origin(position);
 806       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 807       {
 808          ++position;
 809       }
 810       count = (unsigned)::boost::re_detail::distance(origin, position);
 811    }
 812    else
 813    {
 814       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 815       {
 816          ++position;
 817          ++count;
 818       }
 819    }
 820
 821    if(count < rep->min)
 822       return false;
 823
 824    if(greedy)
 825    {
 826       if((rep->leading) && (count < rep->max))
 827          restart = position;
 828       // push backtrack info if available:
 829       if(count - rep->min)
 830          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 831       // jump to next state:
 832       pstate = rep->alt.p;
 833       return true;
 834    }
 835    else
 836    {
 837       // non-greedy, push state and return true if we can skip:
 838       if(count < rep->max)
 839          push_single_repeat(count, rep, position, saved_state_rep_long_set);
 840       pstate = rep->alt.p;
 841       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 842    }
 843 #ifdef __BORLANDC__
 844 #pragma option pop
 845 #endif
 846 #ifdef BOOST_MSVC
 847 #pragma warning(pop)
 848 #endif
 849 }
 850
 851 /****************************************************************************
 852
 853 Unwind and associated proceedures follow, these perform what normal stack
 854 unwinding does in the recursive implementation.
 855
 856 ****************************************************************************/
 857
 858 template <class BidiIterator, class Allocator, class traits>
 859 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
 860 {
 861    static unwind_proc_type const s_unwind_table[14] =
 862    {
 863       &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
 864       &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
 865       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
 866       &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
 867       &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
 868       &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
 869       &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
 870       &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
 871       &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
 872       &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
 873       &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
 874       &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
 875       &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
 876       &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
 877    };
 878
 879    m_recursive_result = have_match;
 880    unwind_proc_type unwinder;
 881    bool cont;
 882    //
 883    // keep unwinding our stack until we have something to do:
 884    //
 885    do
 886    {
 887       unwinder = s_unwind_table[m_backup_state->state_id];
 888       cont = (this->*unwinder)(m_recursive_result);
 889    }while(cont);
 890    //
 891    // return true if we have more states to try:
 892    //
 893    return pstate ? true : false;
 894 }
 895
 896 template <class BidiIterator, class Allocator, class traits>
 897 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
 898 {
 899    pstate = 0;   // nothing left to search
 900    return false; // end of stack nothing more to search
 901 }
 902
 903 template <class BidiIterator, class Allocator, class traits>
 904 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
 905 {
 906    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 907    // restore previous values if no match was found:
 908    if(have_match == false)
 909    {
 910       m_presult->set_first(pmp->sub.first, pmp->index);
 911       m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched);
 912    }
 913 #ifdef BOOST_REGEX_MATCH_EXTRA
 914    //
 915    // we have a match, push the capture information onto the stack:
 916    //
 917    else if(pmp->sub.matched && (match_extra & m_match_flags))
 918       ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
 919 #endif
 920    // unwind stack:
 921    m_backup_state = pmp+1;
 922    boost::re_detail::inplace_destroy(pmp);
 923    return true; // keep looking
 924 }
 925
 926 template <class BidiIterator, class Allocator, class traits>
 927 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
 928 {
 929    boost::re_detail::inplace_destroy(m_backup_state++);
 930    pstate = 0;   // nothing left to search
 931    return false; // end of stack nothing more to search
 932 }
 933
 934 template <class BidiIterator, class Allocator, class traits>
 935 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
 936 {
 937    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 938    pstate = pmp->pstate;
 939    position = pmp->position;
 940    bool result = (r == pmp->positive);
 941    m_recursive_result = pmp->positive ? r : !r;
 942    boost::re_detail::inplace_destroy(pmp++);
 943    m_backup_state = pmp;
 944    return !result; // return false if the assertion was matched to stop search.
 945 }
 946
 947 template <class BidiIterator, class Allocator, class traits>
 948 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
 949 {
 950    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 951    if(!r)
 952    {
 953       pstate = pmp->pstate;
 954       position = pmp->position;
 955    }
 956    boost::re_detail::inplace_destroy(pmp++);
 957    m_backup_state = pmp;
 958    return r;
 959 }
 960
 961 template <class BidiIterator, class Allocator, class traits>
 962 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
 963 {
 964    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 965    boost::re_detail::inplace_destroy(pmp++);
 966    m_backup_state = pmp;
 967    return true; // keep looking
 968 }
 969
 970 template <class BidiIterator, class Allocator, class traits>
 971 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
 972 {
 973    saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
 974    void* condemmed = m_stack_base;
 975    m_stack_base = pmp->base;
 976    m_backup_state = pmp->end;
 977    boost::re_detail::inplace_destroy(pmp);
 978    put_mem_block(condemmed);
 979    return true; // keep looking
 980 }
 981
 982 template <class BidiIterator, class Allocator, class traits>
 983 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
 984 {
 985    saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 986    boost::re_detail::inplace_destroy(p++);
 987    m_backup_state = p;
 988 }
 989
 990 template <class BidiIterator, class Allocator, class traits>
 991 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
 992 {
 993    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 994
 995    // if we have a match, just discard this state:
 996    if(r)
 997    {
 998       destroy_single_repeat();
 999       return true;
1000    }
1001
1002    const re_repeat* rep = pmp->rep;
1003    std::size_t count = pmp->count;
1004    BOOST_ASSERT(rep->next.p != 0);
1005    BOOST_ASSERT(rep->alt.p != 0);
1006
1007    count -= rep->min;
1008
1009    if((m_match_flags & match_partial) && (position == last))
1010       m_has_partial_match = true;
1011
1012    BOOST_ASSERT(count);
1013    position = pmp->last_position;
1014
1015    // backtrack till we can skip out:
1016    do
1017    {
1018       --position;
1019       --count;
1020       ++state_count;
1021    }while(count && !can_start(*position, rep->_map, mask_skip));
1022
1023    // if we've hit base, destroy this state:
1024    if(count == 0)
1025    {
1026          destroy_single_repeat();
1027          if(!can_start(*position, rep->_map, mask_skip))
1028             return true;
1029    }
1030    else
1031    {
1032       pmp->count = count + rep->min;
1033       pmp->last_position = position;
1034    }
1035    pstate = rep->alt.p;
1036    return false;
1037 }
1038
1039 template <class BidiIterator, class Allocator, class traits>
1040 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1041 {
1042    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1043
1044    // if we have a match, just discard this state:
1045    if(r)
1046    {
1047       destroy_single_repeat();
1048       return true;
1049    }
1050
1051    const re_repeat* rep = pmp->rep;
1052    std::size_t count = pmp->count;
1053    BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1054    BOOST_ASSERT(rep->next.p != 0);
1055    BOOST_ASSERT(rep->alt.p != 0);
1056    BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1057
1058    BOOST_ASSERT(count < rep->max);
1059    pstate = rep->next.p;
1060    position = pmp->last_position;
1061
1062    if(position != last)
1063    {
1064       // wind forward until we can skip out of the repeat:
1065       do
1066       {
1067          if(!match_wild())
1068          {
1069             // failed repeat match, discard this state and look for another:
1070             destroy_single_repeat();
1071             return true;
1072          }
1073          ++count;
1074          ++state_count;
1075          pstate = rep->next.p;
1076       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1077    }
1078    if(position == last)
1079    {
1080       // can't repeat any more, remove the pushed state:
1081       destroy_single_repeat();
1082       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1083          m_has_partial_match = true;
1084       if(0 == (rep->can_be_null & mask_skip))
1085          return true;
1086    }
1087    else if(count == rep->max)
1088    {
1089       // can't repeat any more, remove the pushed state:
1090       destroy_single_repeat();
1091       if(!can_start(*position, rep->_map, mask_skip))
1092          return true;
1093    }
1094    else
1095    {
1096       pmp->count = count;
1097       pmp->last_position = position;
1098    }
1099    pstate = rep->alt.p;
1100    return false;
1101 }
1102
1103 template <class BidiIterator, class Allocator, class traits>
1104 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1105 {
1106    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1107
1108    // if we have a match, just discard this state:
1109    if(r)
1110    {
1111       destroy_single_repeat();
1112       return true;
1113    }
1114
1115    const re_repeat* rep = pmp->rep;
1116    std::size_t count = pmp->count;
1117
1118    BOOST_ASSERT(count < rep->max);
1119    position = pmp->last_position;
1120    if(position != last)
1121    {
1122
1123       // wind forward until we can skip out of the repeat:
1124       do
1125       {
1126          ++position;
1127          ++count;
1128          ++state_count;
1129       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1130    }
1131
1132    if(position == last)
1133    {
1134       // can't repeat any more, remove the pushed state:
1135       destroy_single_repeat();
1136       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1137          m_has_partial_match = true;
1138       if(0 == (rep->can_be_null & mask_skip))
1139          return true;
1140    }
1141    else if(count == rep->max)
1142    {
1143       // can't repeat any more, remove the pushed state:
1144       destroy_single_repeat();
1145       if(!can_start(*position, rep->_map, mask_skip))
1146          return true;
1147    }
1148    else
1149    {
1150       pmp->count = count;
1151       pmp->last_position = position;
1152    }
1153    pstate = rep->alt.p;
1154    return false;
1155 }
1156
1157 template <class BidiIterator, class Allocator, class traits>
1158 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1159 {
1160    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1161
1162    // if we have a match, just discard this state:
1163    if(r)
1164    {
1165       destroy_single_repeat();
1166       return true;
1167    }
1168
1169    const re_repeat* rep = pmp->rep;
1170    std::size_t count = pmp->count;
1171    pstate = rep->next.p;
1172    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1173    position = pmp->last_position;
1174
1175    BOOST_ASSERT(rep->type == syntax_element_char_rep);
1176    BOOST_ASSERT(rep->next.p != 0);
1177    BOOST_ASSERT(rep->alt.p != 0);
1178    BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1179    BOOST_ASSERT(count < rep->max);
1180
1181    if(position != last)
1182    {
1183       // wind forward until we can skip out of the repeat:
1184       do
1185       {
1186          if(traits_inst.translate(*position, icase) != what)
1187          {
1188             // failed repeat match, discard this state and look for another:
1189             destroy_single_repeat();
1190             return true;
1191          }
1192          ++count;
1193          ++ position;
1194          ++state_count;
1195          pstate = rep->next.p;
1196       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1197    }
1198    // remember where we got to if this is a leading repeat:
1199    if((rep->leading) && (count < rep->max))
1200       restart = position;
1201    if(position == last)
1202    {
1203       // can't repeat any more, remove the pushed state:
1204       destroy_single_repeat();
1205       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1206          m_has_partial_match = true;
1207       if(0 == (rep->can_be_null & mask_skip))
1208          return true;
1209    }
1210    else if(count == rep->max)
1211    {
1212       // can't repeat any more, remove the pushed state:
1213       destroy_single_repeat();
1214       if(!can_start(*position, rep->_map, mask_skip))
1215          return true;
1216    }
1217    else
1218    {
1219       pmp->count = count;
1220       pmp->last_position = position;
1221    }
1222    pstate = rep->alt.p;
1223    return false;
1224 }
1225
1226 template <class BidiIterator, class Allocator, class traits>
1227 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1228 {
1229    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1230
1231    // if we have a match, just discard this state:
1232    if(r)
1233    {
1234       destroy_single_repeat();
1235       return true;
1236    }
1237
1238    const re_repeat* rep = pmp->rep;
1239    std::size_t count = pmp->count;
1240    pstate = rep->next.p;
1241    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1242    position = pmp->last_position;
1243
1244    BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1245    BOOST_ASSERT(rep->next.p != 0);
1246    BOOST_ASSERT(rep->alt.p != 0);
1247    BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1248    BOOST_ASSERT(count < rep->max);
1249
1250    if(position != last)
1251    {
1252       // wind forward until we can skip out of the repeat:
1253       do
1254       {
1255          if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1256          {
1257             // failed repeat match, discard this state and look for another:
1258             destroy_single_repeat();
1259             return true;
1260          }
1261          ++count;
1262          ++ position;
1263          ++state_count;
1264          pstate = rep->next.p;
1265       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1266    }
1267    // remember where we got to if this is a leading repeat:
1268    if((rep->leading) && (count < rep->max))
1269       restart = position;
1270    if(position == last)
1271    {
1272       // can't repeat any more, remove the pushed state:
1273       destroy_single_repeat();
1274       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1275          m_has_partial_match = true;
1276       if(0 == (rep->can_be_null & mask_skip))
1277          return true;
1278    }
1279    else if(count == rep->max)
1280    {
1281       // can't repeat any more, remove the pushed state:
1282       destroy_single_repeat();
1283       if(!can_start(*position, rep->_map, mask_skip))
1284          return true;
1285    }
1286    else
1287    {
1288       pmp->count = count;
1289       pmp->last_position = position;
1290    }
1291    pstate = rep->alt.p;
1292    return false;
1293 }
1294
1295 template <class BidiIterator, class Allocator, class traits>
1296 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1297 {
1298    typedef typename traits::char_class_type mask_type;
1299    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1300
1301    // if we have a match, just discard this state:
1302    if(r)
1303    {
1304       destroy_single_repeat();
1305       return true;
1306    }
1307
1308    const re_repeat* rep = pmp->rep;
1309    std::size_t count = pmp->count;
1310    pstate = rep->next.p;
1311    const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate);
1312    position = pmp->last_position;
1313
1314    BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1315    BOOST_ASSERT(rep->next.p != 0);
1316    BOOST_ASSERT(rep->alt.p != 0);
1317    BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1318    BOOST_ASSERT(count < rep->max);
1319
1320    if(position != last)
1321    {
1322       // wind forward until we can skip out of the repeat:
1323       do
1324       {
1325          if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1326          {
1327             // failed repeat match, discard this state and look for another:
1328             destroy_single_repeat();
1329             return true;
1330          }
1331          ++position;
1332          ++count;
1333          ++state_count;
1334          pstate = rep->next.p;
1335       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1336    }
1337    // remember where we got to if this is a leading repeat:
1338    if((rep->leading) && (count < rep->max))
1339       restart = position;
1340    if(position == last)
1341    {
1342       // can't repeat any more, remove the pushed state:
1343       destroy_single_repeat();
1344       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1345          m_has_partial_match = true;
1346       if(0 == (rep->can_be_null & mask_skip))
1347          return true;
1348    }
1349    else if(count == rep->max)
1350    {
1351       // can't repeat any more, remove the pushed state:
1352       destroy_single_repeat();
1353       if(!can_start(*position, rep->_map, mask_skip))
1354          return true;
1355    }
1356    else
1357    {
1358       pmp->count = count;
1359       pmp->last_position = position;
1360    }
1361    pstate = rep->alt.p;
1362    return false;
1363 }
1364
1365 template <class BidiIterator, class Allocator, class traits>
1366 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1367 {
1368    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1369    if(!r)
1370    {
1371       position = pmp->position;
1372       pstate = pmp->pstate;
1373       ++(*next_count);
1374    }
1375    boost::re_detail::inplace_destroy(pmp++);
1376    m_backup_state = pmp;
1377    return r;
1378 }
1379
1380 } // namespace re_detail
1381 } // namespace boost
1382
1383 #ifdef BOOST_MSVC
1384 #  pragma warning(pop)
1385 #endif
1386
1387 #ifdef BOOST_MSVC
1388 #pragma warning(push)
1389 #pragma warning(disable: 4103)
1390 #endif
1391 #ifdef BOOST_HAS_ABI_HEADERS
1392 #  include BOOST_ABI_SUFFIX
1393 #endif
1394 #ifdef BOOST_MSVC
1395 #pragma warning(pop)
1396 #endif
1397
1398 #endif
1399
1400