boost/boost/regex/v4/perl_matcher_non_recursive.hpp

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