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