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 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) : 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 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, 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(take_first || (next_count->get_id() != rep->id))
 481    {
 482       // we're moving to a different repeat from the last
 483       // one, so set up a counter object:
 484       push_repeater_count(rep->id, &next_count);
 485    }
 486    //
 487    // If we've had at least one repeat already, and the last one
 488    // matched the NULL string then set the repeat count to
 489    // maximum:
 490    //
 491    next_count->check_null_repeat(position, rep->max);
 492
 493    if(next_count->get_count() < rep->min)
 494    {
 495       // we must take the repeat:
 496       if(take_first)
 497       {
 498          // increase the counter:
 499          ++(*next_count);
 500          pstate = rep->next.p;
 501          return true;
 502       }
 503       return false;
 504    }
 505
 506    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 507    if(greedy)
 508    {
 509       // try and take the repeat if we can:
 510       if((next_count->get_count() < rep->max) && take_first)
 511       {
 512          if(take_second)
 513          {
 514             // store position in case we fail:
 515             push_alt(rep->alt.p);
 516          }
 517          // increase the counter:
 518          ++(*next_count);
 519          pstate = rep->next.p;
 520          return true;
 521       }
 522       else if(take_second)
 523       {
 524          pstate = rep->alt.p;
 525          return true;
 526       }
 527       return false; // can't take anything, fail...
 528    }
 529    else // non-greedy
 530    {
 531       // try and skip the repeat if we can:
 532       if(take_second)
 533       {
 534          if((next_count->get_count() < rep->max) && take_first)
 535          {
 536             // store position in case we fail:
 537             push_non_greedy_repeat(rep->next.p);
 538          }
 539          pstate = rep->alt.p;
 540          return true;
 541       }
 542       if((next_count->get_count() < rep->max) && take_first)
 543       {
 544          // increase the counter:
 545          ++(*next_count);
 546          pstate = rep->next.p;
 547          return true;
 548       }
 549    }
 550    return false;
 551 #ifdef __BORLANDC__
 552 #pragma option pop
 553 #endif
 554 #ifdef BOOST_MSVC
 555 #pragma warning(pop)
 556 #endif
 557 }
 558
 559 template <class BidiIterator, class Allocator, class traits>
 560 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 561 {
 562    unsigned count = 0;
 563    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 564    re_syntax_base* psingle = rep->next.p;
 565    // match compulsary repeats first:
 566    while(count < rep->min)
 567    {
 568       pstate = psingle;
 569       if(!match_wild())
 570          return false;
 571       ++count;
 572    }
 573    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 574    if(greedy)
 575    {
 576       // repeat for as long as we can:
 577       while(count < rep->max)
 578       {
 579          pstate = psingle;
 580          if(!match_wild())
 581             break;
 582          ++count;
 583       }
 584       // remember where we got to if this is a leading repeat:
 585       if((rep->leading) && (count < rep->max))
 586          restart = position;
 587       // push backtrack info if available:
 588       if(count - rep->min)
 589          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 590       // jump to next state:
 591       pstate = rep->alt.p;
 592       return true;
 593    }
 594    else
 595    {
 596       // non-greedy, push state and return true if we can skip:
 597       if(count < rep->max)
 598          push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
 599       pstate = rep->alt.p;
 600       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 601    }
 602 }
 603
 604 template <class BidiIterator, class Allocator, class traits>
 605 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 606 {
 607    if(m_match_flags & match_not_dot_null)
 608       return match_dot_repeat_slow();
 609    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 610       return match_dot_repeat_slow();
 611
 612    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 613    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 614    unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
 615    if(rep->min > count)
 616    {
 617       position = last;
 618       return false;  // not enough text left to match
 619    }
 620    std::advance(position, count);
 621
 622    if(greedy)
 623    {
 624       if((rep->leading) && (count < rep->max))
 625          restart = position;
 626       // push backtrack info if available:
 627       if(count - rep->min)
 628          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 629       // jump to next state:
 630       pstate = rep->alt.p;
 631       return true;
 632    }
 633    else
 634    {
 635       // non-greedy, push state and return true if we can skip:
 636       if(count < rep->max)
 637          push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
 638       pstate = rep->alt.p;
 639       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 640    }
 641 }
 642
 643 template <class BidiIterator, class Allocator, class traits>
 644 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 645 {
 646 #ifdef BOOST_MSVC
 647 #pragma warning(push)
 648 #pragma warning(disable:4127)
 649 #endif
 650 #ifdef __BORLANDC__
 651 #pragma option push -w-8008 -w-8066 -w-8004
 652 #endif
 653    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 654    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 655    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 656    std::size_t count = 0;
 657    //
 658    // start by working out how much we can skip:
 659    //
 660    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 661    std::size_t desired = greedy ? rep->max : rep->min;
 662    if(::boost::is_random_access_iterator<BidiIterator>::value)
 663    {
 664       BidiIterator end = position;
 665       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 666       BidiIterator origin(position);
 667       while((position != end) && (traits_inst.translate(*position, icase) == what))
 668       {
 669          ++position;
 670       }
 671       count = (unsigned)::boost::re_detail::distance(origin, position);
 672    }
 673    else
 674    {
 675       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 676       {
 677          ++position;
 678          ++count;
 679       }
 680    }
 681
 682    if(count < rep->min)
 683       return false;
 684
 685    if(greedy)
 686    {
 687       if((rep->leading) && (count < rep->max))
 688          restart = position;
 689       // push backtrack info if available:
 690       if(count - rep->min)
 691          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 692       // jump to next state:
 693       pstate = rep->alt.p;
 694       return true;
 695    }
 696    else
 697    {
 698       // non-greedy, push state and return true if we can skip:
 699       if(count < rep->max)
 700          push_single_repeat(count, rep, position, saved_state_rep_char);
 701       pstate = rep->alt.p;
 702       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 703    }
 704 #ifdef __BORLANDC__
 705 #pragma option pop
 706 #endif
 707 #ifdef BOOST_MSVC
 708 #pragma warning(pop)
 709 #endif
 710 }
 711
 712 template <class BidiIterator, class Allocator, class traits>
 713 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 714 {
 715 #ifdef BOOST_MSVC
 716 #pragma warning(push)
 717 #pragma warning(disable:4127)
 718 #endif
 719 #ifdef __BORLANDC__
 720 #pragma option push -w-8008 -w-8066 -w-8004
 721 #endif
 722    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 723    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 724    std::size_t count = 0;
 725    //
 726    // start by working out how much we can skip:
 727    //
 728    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 729    std::size_t desired = greedy ? rep->max : rep->min;
 730    if(::boost::is_random_access_iterator<BidiIterator>::value)
 731    {
 732       BidiIterator end = position;
 733       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 734       BidiIterator origin(position);
 735       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 736       {
 737          ++position;
 738       }
 739       count = (unsigned)::boost::re_detail::distance(origin, position);
 740    }
 741    else
 742    {
 743       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 744       {
 745          ++position;
 746          ++count;
 747       }
 748    }
 749
 750    if(count < rep->min)
 751       return false;
 752
 753    if(greedy)
 754    {
 755       if((rep->leading) && (count < rep->max))
 756          restart = position;
 757       // push backtrack info if available:
 758       if(count - rep->min)
 759          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 760       // jump to next state:
 761       pstate = rep->alt.p;
 762       return true;
 763    }
 764    else
 765    {
 766       // non-greedy, push state and return true if we can skip:
 767       if(count < rep->max)
 768          push_single_repeat(count, rep, position, saved_state_rep_short_set);
 769       pstate = rep->alt.p;
 770       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 771    }
 772 #ifdef __BORLANDC__
 773 #pragma option pop
 774 #endif
 775 #ifdef BOOST_MSVC
 776 #pragma warning(pop)
 777 #endif
 778 }
 779
 780 template <class BidiIterator, class Allocator, class traits>
 781 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 782 {
 783 #ifdef BOOST_MSVC
 784 #pragma warning(push)
 785 #pragma warning(disable:4127)
 786 #endif
 787 #ifdef __BORLANDC__
 788 #pragma option push -w-8008 -w-8066 -w-8004
 789 #endif
 790    typedef typename traits::char_class_type mask_type;
 791    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 792    const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate->next.p);
 793    std::size_t count = 0;
 794    //
 795    // start by working out how much we can skip:
 796    //
 797    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 798    std::size_t desired = greedy ? rep->max : rep->min;
 799    if(::boost::is_random_access_iterator<BidiIterator>::value)
 800    {
 801       BidiIterator end = position;
 802       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 803       BidiIterator origin(position);
 804       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 805       {
 806          ++position;
 807       }
 808       count = (unsigned)::boost::re_detail::distance(origin, position);
 809    }
 810    else
 811    {
 812       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 813       {
 814          ++position;
 815          ++count;
 816       }
 817    }
 818
 819    if(count < rep->min)
 820       return false;
 821
 822    if(greedy)
 823    {
 824       if((rep->leading) && (count < rep->max))
 825          restart = position;
 826       // push backtrack info if available:
 827       if(count - rep->min)
 828          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 829       // jump to next state:
 830       pstate = rep->alt.p;
 831       return true;
 832    }
 833    else
 834    {
 835       // non-greedy, push state and return true if we can skip:
 836       if(count < rep->max)
 837          push_single_repeat(count, rep, position, saved_state_rep_long_set);
 838       pstate = rep->alt.p;
 839       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 840    }
 841 #ifdef __BORLANDC__
 842 #pragma option pop
 843 #endif
 844 #ifdef BOOST_MSVC
 845 #pragma warning(pop)
 846 #endif
 847 }
 848
 849 /****************************************************************************
 850
 851 Unwind and associated proceedures follow, these perform what normal stack
 852 unwinding does in the recursive implementation.
 853
 854 ****************************************************************************/
 855
 856 template <class BidiIterator, class Allocator, class traits>
 857 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
 858 {
 859    static unwind_proc_type const s_unwind_table[14] =
 860    {
 861       &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
 862       &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
 863       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
 864       &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
 865       &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
 866       &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
 867       &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
 868       &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
 869       &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
 870       &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
 871       &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
 872       &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
 873       &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
 874       &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
 875    };
 876
 877    m_recursive_result = have_match;
 878    unwind_proc_type unwinder;
 879    bool cont;
 880    //
 881    // keep unwinding our stack until we have something to do:
 882    //
 883    do
 884    {
 885       unwinder = s_unwind_table[m_backup_state->id];
 886       cont = (this->*unwinder)(m_recursive_result);
 887    }while(cont);
 888    //
 889    // return true if we have more states to try:
 890    //
 891    return pstate ? true : false;
 892 }
 893
 894 template <class BidiIterator, class Allocator, class traits>
 895 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
 896 {
 897    pstate = 0;   // nothing left to search
 898    return false; // end of stack nothing more to search
 899 }
 900
 901 template <class BidiIterator, class Allocator, class traits>
 902 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
 903 {
 904    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 905    // restore previous values if no match was found:
 906    if(have_match == false)
 907    {
 908       m_presult->set_first(pmp->sub.first, pmp->index);
 909       m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched);
 910    }
 911 #ifdef BOOST_REGEX_MATCH_EXTRA
 912    //
 913    // we have a match, push the capture information onto the stack:
 914    //
 915    else if(pmp->sub.matched && (match_extra & m_match_flags))
 916       ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
 917 #endif
 918    // unwind stack:
 919    m_backup_state = pmp+1;
 920    boost::re_detail::inplace_destroy(pmp);
 921    return true; // keep looking
 922 }
 923
 924 template <class BidiIterator, class Allocator, class traits>
 925 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
 926 {
 927    boost::re_detail::inplace_destroy(m_backup_state++);
 928    pstate = 0;   // nothing left to search
 929    return false; // end of stack nothing more to search
 930 }
 931
 932 template <class BidiIterator, class Allocator, class traits>
 933 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
 934 {
 935    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 936    pstate = pmp->pstate;
 937    position = pmp->position;
 938    bool result = (r == pmp->positive);
 939    m_recursive_result = pmp->positive ? r : !r;
 940    boost::re_detail::inplace_destroy(pmp++);
 941    m_backup_state = pmp;
 942    return !result; // return false if the assertion was matched to stop search.
 943 }
 944
 945 template <class BidiIterator, class Allocator, class traits>
 946 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
 947 {
 948    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 949    if(!r)
 950    {
 951       pstate = pmp->pstate;
 952       position = pmp->position;
 953    }
 954    boost::re_detail::inplace_destroy(pmp++);
 955    m_backup_state = pmp;
 956    return r;
 957 }
 958
 959 template <class BidiIterator, class Allocator, class traits>
 960 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
 961 {
 962    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 963    boost::re_detail::inplace_destroy(pmp++);
 964    m_backup_state = pmp;
 965    return true; // keep looking
 966 }
 967
 968 template <class BidiIterator, class Allocator, class traits>
 969 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
 970 {
 971    saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
 972    void* condemmed = m_stack_base;
 973    m_stack_base = pmp->base;
 974    m_backup_state = pmp->end;
 975    boost::re_detail::inplace_destroy(pmp);
 976    put_mem_block(condemmed);
 977    return true; // keep looking
 978 }
 979
 980 template <class BidiIterator, class Allocator, class traits>
 981 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
 982 {
 983    saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 984    boost::re_detail::inplace_destroy(p++);
 985    m_backup_state = p;
 986 }
 987
 988 template <class BidiIterator, class Allocator, class traits>
 989 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
 990 {
 991    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 992
 993    // if we have a match, just discard this state:
 994    if(r)
 995    {
 996       destroy_single_repeat();
 997       return true;
 998    }
 999
1000    const re_repeat* rep = pmp->rep;
1001    std::size_t count = pmp->count;
1002    BOOST_ASSERT(rep->next.p != 0);
1003    BOOST_ASSERT(rep->alt.p != 0);
1004
1005    count -= rep->min;
1006
1007    if((m_match_flags & match_partial) && (position == last))
1008       m_has_partial_match = true;
1009
1010    BOOST_ASSERT(count);
1011    position = pmp->last_position;
1012
1013    // backtrack till we can skip out:
1014    do
1015    {
1016       --position;
1017       --count;
1018       ++state_count;
1019    }while(count && !can_start(*position, rep->_map, mask_skip));
1020
1021    // if we've hit base, destroy this state:
1022    if(count == 0)
1023    {
1024          destroy_single_repeat();
1025          if(!can_start(*position, rep->_map, mask_skip))
1026             return true;
1027    }
1028    else
1029    {
1030       pmp->count = count + rep->min;
1031       pmp->last_position = position;
1032    }
1033    pstate = rep->alt.p;
1034    return false;
1035 }
1036
1037 template <class BidiIterator, class Allocator, class traits>
1038 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1039 {
1040    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1041
1042    // if we have a match, just discard this state:
1043    if(r)
1044    {
1045       destroy_single_repeat();
1046       return true;
1047    }
1048
1049    const re_repeat* rep = pmp->rep;
1050    std::size_t count = pmp->count;
1051    BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1052    BOOST_ASSERT(rep->next.p != 0);
1053    BOOST_ASSERT(rep->alt.p != 0);
1054    BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1055
1056    BOOST_ASSERT(count < rep->max);
1057    pstate = rep->next.p;
1058    position = pmp->last_position;
1059
1060    if(position != last)
1061    {
1062       // wind forward until we can skip out of the repeat:
1063       do
1064       {
1065          if(!match_wild())
1066          {
1067             // failed repeat match, discard this state and look for another:
1068             destroy_single_repeat();
1069             return true;
1070          }
1071          ++count;
1072          ++state_count;
1073          pstate = rep->next.p;
1074       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1075    }
1076    if(position == last)
1077    {
1078       // can't repeat any more, remove the pushed state:
1079       destroy_single_repeat();
1080       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1081          m_has_partial_match = true;
1082       if(0 == (rep->can_be_null & mask_skip))
1083          return true;
1084    }
1085    else if(count == rep->max)
1086    {
1087       // can't repeat any more, remove the pushed state:
1088       destroy_single_repeat();
1089       if(!can_start(*position, rep->_map, mask_skip))
1090          return true;
1091    }
1092    else
1093    {
1094       pmp->count = count;
1095       pmp->last_position = position;
1096    }
1097    pstate = rep->alt.p;
1098    return false;
1099 }
1100
1101 template <class BidiIterator, class Allocator, class traits>
1102 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1103 {
1104    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1105
1106    // if we have a match, just discard this state:
1107    if(r)
1108    {
1109       destroy_single_repeat();
1110       return true;
1111    }
1112
1113    const re_repeat* rep = pmp->rep;
1114    std::size_t count = pmp->count;
1115
1116    BOOST_ASSERT(count < rep->max);
1117    position = pmp->last_position;
1118    if(position != last)
1119    {
1120
1121       // wind forward until we can skip out of the repeat:
1122       do
1123       {
1124          ++position;
1125          ++count;
1126          ++state_count;
1127       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1128    }
1129
1130    if(position == last)
1131    {
1132       // can't repeat any more, remove the pushed state:
1133       destroy_single_repeat();
1134       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1135          m_has_partial_match = true;
1136       if(0 == (rep->can_be_null & mask_skip))
1137          return true;
1138    }
1139    else if(count == rep->max)
1140    {
1141       // can't repeat any more, remove the pushed state:
1142       destroy_single_repeat();
1143       if(!can_start(*position, rep->_map, mask_skip))
1144          return true;
1145    }
1146    else
1147    {
1148       pmp->count = count;
1149       pmp->last_position = position;
1150    }
1151    pstate = rep->alt.p;
1152    return false;
1153 }
1154
1155 template <class BidiIterator, class Allocator, class traits>
1156 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1157 {
1158    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1159
1160    // if we have a match, just discard this state:
1161    if(r)
1162    {
1163       destroy_single_repeat();
1164       return true;
1165    }
1166
1167    const re_repeat* rep = pmp->rep;
1168    std::size_t count = pmp->count;
1169    pstate = rep->next.p;
1170    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1171    position = pmp->last_position;
1172
1173    BOOST_ASSERT(rep->type == syntax_element_char_rep);
1174    BOOST_ASSERT(rep->next.p != 0);
1175    BOOST_ASSERT(rep->alt.p != 0);
1176    BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1177    BOOST_ASSERT(count < rep->max);
1178
1179    if(position != last)
1180    {
1181       // wind forward until we can skip out of the repeat:
1182       do
1183       {
1184          if(traits_inst.translate(*position, icase) != what)
1185          {
1186             // failed repeat match, discard this state and look for another:
1187             destroy_single_repeat();
1188             return true;
1189          }
1190          ++count;
1191          ++ position;
1192          ++state_count;
1193          pstate = rep->next.p;
1194       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1195    }
1196    // remember where we got to if this is a leading repeat:
1197    if((rep->leading) && (count < rep->max))
1198       restart = position;
1199    if(position == last)
1200    {
1201       // can't repeat any more, remove the pushed state:
1202       destroy_single_repeat();
1203       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1204          m_has_partial_match = true;
1205       if(0 == (rep->can_be_null & mask_skip))
1206          return true;
1207    }
1208    else if(count == rep->max)
1209    {
1210       // can't repeat any more, remove the pushed state:
1211       destroy_single_repeat();
1212       if(!can_start(*position, rep->_map, mask_skip))
1213          return true;
1214    }
1215    else
1216    {
1217       pmp->count = count;
1218       pmp->last_position = position;
1219    }
1220    pstate = rep->alt.p;
1221    return false;
1222 }
1223
1224 template <class BidiIterator, class Allocator, class traits>
1225 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1226 {
1227    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1228
1229    // if we have a match, just discard this state:
1230    if(r)
1231    {
1232       destroy_single_repeat();
1233       return true;
1234    }
1235
1236    const re_repeat* rep = pmp->rep;
1237    std::size_t count = pmp->count;
1238    pstate = rep->next.p;
1239    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1240    position = pmp->last_position;
1241
1242    BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1243    BOOST_ASSERT(rep->next.p != 0);
1244    BOOST_ASSERT(rep->alt.p != 0);
1245    BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1246    BOOST_ASSERT(count < rep->max);
1247
1248    if(position != last)
1249    {
1250       // wind forward until we can skip out of the repeat:
1251       do
1252       {
1253          if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1254          {
1255             // failed repeat match, discard this state and look for another:
1256             destroy_single_repeat();
1257             return true;
1258          }
1259          ++count;
1260          ++ position;
1261          ++state_count;
1262          pstate = rep->next.p;
1263       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1264    }
1265    // remember where we got to if this is a leading repeat:
1266    if((rep->leading) && (count < rep->max))
1267       restart = position;
1268    if(position == last)
1269    {
1270       // can't repeat any more, remove the pushed state:
1271       destroy_single_repeat();
1272       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1273          m_has_partial_match = true;
1274       if(0 == (rep->can_be_null & mask_skip))
1275          return true;
1276    }
1277    else if(count == rep->max)
1278    {
1279       // can't repeat any more, remove the pushed state:
1280       destroy_single_repeat();
1281       if(!can_start(*position, rep->_map, mask_skip))
1282          return true;
1283    }
1284    else
1285    {
1286       pmp->count = count;
1287       pmp->last_position = position;
1288    }
1289    pstate = rep->alt.p;
1290    return false;
1291 }
1292
1293 template <class BidiIterator, class Allocator, class traits>
1294 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1295 {
1296    typedef typename traits::char_class_type mask_type;
1297    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1298
1299    // if we have a match, just discard this state:
1300    if(r)
1301    {
1302       destroy_single_repeat();
1303       return true;
1304    }
1305
1306    const re_repeat* rep = pmp->rep;
1307    std::size_t count = pmp->count;
1308    pstate = rep->next.p;
1309    const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate);
1310    position = pmp->last_position;
1311
1312    BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1313    BOOST_ASSERT(rep->next.p != 0);
1314    BOOST_ASSERT(rep->alt.p != 0);
1315    BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1316    BOOST_ASSERT(count < rep->max);
1317
1318    if(position != last)
1319    {
1320       // wind forward until we can skip out of the repeat:
1321       do
1322       {
1323          if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1324          {
1325             // failed repeat match, discard this state and look for another:
1326             destroy_single_repeat();
1327             return true;
1328          }
1329          ++position;
1330          ++count;
1331          ++state_count;
1332          pstate = rep->next.p;
1333       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1334    }
1335    // remember where we got to if this is a leading repeat:
1336    if((rep->leading) && (count < rep->max))
1337       restart = position;
1338    if(position == last)
1339    {
1340       // can't repeat any more, remove the pushed state:
1341       destroy_single_repeat();
1342       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1343          m_has_partial_match = true;
1344       if(0 == (rep->can_be_null & mask_skip))
1345          return true;
1346    }
1347    else if(count == rep->max)
1348    {
1349       // can't repeat any more, remove the pushed state:
1350       destroy_single_repeat();
1351       if(!can_start(*position, rep->_map, mask_skip))
1352          return true;
1353    }
1354    else
1355    {
1356       pmp->count = count;
1357       pmp->last_position = position;
1358    }
1359    pstate = rep->alt.p;
1360    return false;
1361 }
1362
1363 template <class BidiIterator, class Allocator, class traits>
1364 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1365 {
1366    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1367    if(!r)
1368    {
1369       position = pmp->position;
1370       pstate = pmp->pstate;
1371       ++(*next_count);
1372    }
1373    boost::re_detail::inplace_destroy(pmp++);
1374    m_backup_state = pmp;
1375    return r;
1376 }
1377
1378 } // namespace re_detail
1379 } // namespace boost
1380
1381 #ifdef BOOST_MSVC
1382 #  pragma warning(pop)
1383 #endif
1384
1385 #ifdef BOOST_MSVC
1386 #pragma warning(push)
1387 #pragma warning(disable: 4103)
1388 #endif
1389 #ifdef BOOST_HAS_ABI_HEADERS
1390 #  include BOOST_ABI_SUFFIX
1391 #endif
1392 #ifdef BOOST_MSVC
1393 #pragma warning(pop)
1394 #endif
1395
1396 #endif
1397
1398