boost/boost/regex/v4/perl_matcher_non_recursive.hpp

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