ceph/src/boost/libs/regex/include/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 4706)
  38 #endif
  39
  40 namespace boost{
  41 namespace BOOST_REGEX_DETAIL_NS{
  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, int current_recursion_id)
  91       : saved_state(saved_state_repeater_count), count(i, s, start, current_recursion_id){}
  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 struct saved_change_case : public saved_state
 142 {
 143    bool icase;
 144    saved_change_case(bool c) : saved_state(18), icase(c) {}
 145 };
 146
 147 template <class BidiIterator, class Allocator, class traits>
 148 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
 149 {
 150    static matcher_proc_type const s_match_vtable[34] =
 151    {
 152       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
 153       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
 154       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
 155       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
 156       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
 157       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
 158       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
 159       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
 160       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
 161       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
 162       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
 163       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
 164       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
 165       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
 166       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
 167       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
 168       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
 169       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
 170       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
 171       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
 172       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
 173       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
 174       // Although this next line *should* be evaluated at compile time, in practice
 175       // some compilers (VC++) emit run-time initialisation which breaks thread
 176       // safety, so use a dispatch function instead:
 177       //(::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),
 178       &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
 179       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
 180       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
 181       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
 182       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
 183       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
 184       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
 185       &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
 186       &perl_matcher<BidiIterator, Allocator, traits>::match_fail,
 187       &perl_matcher<BidiIterator, Allocator, traits>::match_accept,
 188       &perl_matcher<BidiIterator, Allocator, traits>::match_commit,
 189       &perl_matcher<BidiIterator, Allocator, traits>::match_then,
 190    };
 191
 192    push_recursion_stopper();
 193    do{
 194       while(pstate)
 195       {
 196          matcher_proc_type proc = s_match_vtable[pstate->type];
 197          ++state_count;
 198          if(!(this->*proc)())
 199          {
 200             if(state_count > max_state_count)
 201                raise_error(traits_inst, regex_constants::error_complexity);
 202             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 203                m_has_partial_match = true;
 204             bool successful_unwind = unwind(false);
 205             if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 206                m_has_partial_match = true;
 207             if(false == successful_unwind)
 208                return m_recursive_result;
 209          }
 210       }
 211    }while(unwind(true));
 212    return m_recursive_result;
 213 }
 214
 215 template <class BidiIterator, class Allocator, class traits>
 216 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
 217 {
 218    if(used_block_count)
 219    {
 220       --used_block_count;
 221       saved_state* stack_base;
 222       saved_state* backup_state;
 223       stack_base = static_cast<saved_state*>(get_mem_block());
 224       backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);
 225       saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);
 226       --block;
 227       (void) new (block) saved_extra_block(m_stack_base, m_backup_state);
 228       m_stack_base = stack_base;
 229       m_backup_state = block;
 230    }
 231    else
 232       raise_error(traits_inst, regex_constants::error_stack);
 233 }
 234
 235 template <class BidiIterator, class Allocator, class traits>
 236 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
 237 {
 238    //BOOST_ASSERT(index);
 239    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 240    --pmp;
 241    if(pmp < m_stack_base)
 242    {
 243       extend_stack();
 244       pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
 245       --pmp;
 246    }
 247    (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
 248    m_backup_state = pmp;
 249 }
 250
 251 template <class BidiIterator, class Allocator, class traits>
 252 inline void perl_matcher<BidiIterator, Allocator, traits>::push_case_change(bool c)
 253 {
 254    //BOOST_ASSERT(index);
 255    saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
 256    --pmp;
 257    if(pmp < m_stack_base)
 258    {
 259       extend_stack();
 260       pmp = static_cast<saved_change_case*>(m_backup_state);
 261       --pmp;
 262    }
 263    (void) new (pmp)saved_change_case(c);
 264    m_backup_state = pmp;
 265 }
 266
 267 template <class BidiIterator, class Allocator, class traits>
 268 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
 269 {
 270    saved_state* pmp = m_backup_state;
 271    --pmp;
 272    if(pmp < m_stack_base)
 273    {
 274       extend_stack();
 275       pmp = m_backup_state;
 276       --pmp;
 277    }
 278    (void) new (pmp)saved_state(saved_type_recurse);
 279    m_backup_state = pmp;
 280 }
 281
 282 template <class BidiIterator, class Allocator, class traits>
 283 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
 284 {
 285    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 286    --pmp;
 287    if(pmp < m_stack_base)
 288    {
 289       extend_stack();
 290       pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
 291       --pmp;
 292    }
 293    (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
 294    m_backup_state = pmp;
 295 }
 296
 297 template <class BidiIterator, class Allocator, class traits>
 298 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
 299 {
 300    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 301    --pmp;
 302    if(pmp < m_stack_base)
 303    {
 304       extend_stack();
 305       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 306       --pmp;
 307    }
 308    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
 309    m_backup_state = pmp;
 310 }
 311
 312 template <class BidiIterator, class Allocator, class traits>
 313 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
 314 {
 315    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 316    --pmp;
 317    if(pmp < m_stack_base)
 318    {
 319       extend_stack();
 320       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
 321       --pmp;
 322    }
 323    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
 324    m_backup_state = pmp;
 325 }
 326
 327 template <class BidiIterator, class Allocator, class traits>
 328 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
 329 {
 330    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 331    --pmp;
 332    if(pmp < m_stack_base)
 333    {
 334       extend_stack();
 335       pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
 336       --pmp;
 337    }
 338    (void) new (pmp)saved_repeater<BidiIterator>(i, s, position, this->recursion_stack.size() ? this->recursion_stack.back().idx : (INT_MIN + 3));
 339    m_backup_state = pmp;
 340 }
 341
 342 template <class BidiIterator, class Allocator, class traits>
 343 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
 344 {
 345    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 346    --pmp;
 347    if(pmp < m_stack_base)
 348    {
 349       extend_stack();
 350       pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
 351       --pmp;
 352    }
 353    (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
 354    m_backup_state = pmp;
 355 }
 356
 357 template <class BidiIterator, class Allocator, class traits>
 358 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int idx, const re_syntax_base* p, results_type* presults)
 359 {
 360    saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
 361    --pmp;
 362    if(pmp < m_stack_base)
 363    {
 364       extend_stack();
 365       pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
 366       --pmp;
 367    }
 368    (void) new (pmp)saved_recursion<results_type>(idx, p, presults);
 369    m_backup_state = pmp;
 370 }
 371
 372 template <class BidiIterator, class Allocator, class traits>
 373 bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
 374 {
 375    // change our case sensitivity:
 376    push_case_change(this->icase);
 377    this->icase = static_cast<const re_case*>(pstate)->icase;
 378    pstate = pstate->next.p;
 379    return true;
 380 }
 381
 382 template <class BidiIterator, class Allocator, class traits>
 383 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
 384 {
 385    int index = static_cast<const re_brace*>(pstate)->index;
 386    icase = static_cast<const re_brace*>(pstate)->icase;
 387    switch(index)
 388    {
 389    case 0:
 390       pstate = pstate->next.p;
 391       break;
 392    case -1:
 393    case -2:
 394       {
 395          // forward lookahead assert:
 396          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 397          pstate = pstate->next.p->next.p;
 398          push_assertion(next_pstate, index == -1);
 399          break;
 400       }
 401    case -3:
 402       {
 403          // independent sub-expression, currently this is always recursive:
 404          bool old_independent = m_independent;
 405          m_independent = true;
 406          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 407          pstate = pstate->next.p->next.p;
 408          bool r = match_all_states();
 409          if(!r && !m_independent)
 410          {
 411             // Must be unwinding from a COMMIT/SKIP/PRUNE and the independent
 412             // sub failed, need to unwind everything else:
 413             while(unwind(false));
 414             return false;
 415          }
 416          pstate = next_pstate;
 417          m_independent = old_independent;
 418 #ifdef BOOST_REGEX_MATCH_EXTRA
 419          if(r && (m_match_flags & match_extra))
 420          {
 421             //
 422             // our captures have been stored in *m_presult
 423             // we need to unpack them, and insert them
 424             // back in the right order when we unwind the stack:
 425             //
 426             match_results<BidiIterator, Allocator> temp_match(*m_presult);
 427             unsigned i;
 428             for(i = 0; i < temp_match.size(); ++i)
 429                (*m_presult)[i].get_captures().clear();
 430             // match everything else:
 431             r = match_all_states();
 432             // now place the stored captures back:
 433             for(i = 0; i < temp_match.size(); ++i)
 434             {
 435                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
 436                seq& s1 = (*m_presult)[i].get_captures();
 437                const seq& s2 = temp_match[i].captures();
 438                s1.insert(
 439                   s1.end(),
 440                   s2.begin(),
 441                   s2.end());
 442             }
 443          }
 444 #endif
 445          return r;
 446       }
 447    case -4:
 448       {
 449       // conditional expression:
 450       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
 451       BOOST_ASSERT(alt->type == syntax_element_alt);
 452       pstate = alt->next.p;
 453       if(pstate->type == syntax_element_assert_backref)
 454       {
 455          if(!match_assert_backref())
 456             pstate = alt->alt.p;
 457          break;
 458       }
 459       else
 460       {
 461          // zero width assertion, have to match this recursively:
 462          BOOST_ASSERT(pstate->type == syntax_element_startmark);
 463          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
 464          BidiIterator saved_position = position;
 465          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 466          pstate = pstate->next.p->next.p;
 467          bool r = match_all_states();
 468          position = saved_position;
 469          if(negated)
 470             r = !r;
 471          if(r)
 472             pstate = next_pstate;
 473          else
 474             pstate = alt->alt.p;
 475          break;
 476       }
 477       }
 478    case -5:
 479       {
 480          push_matched_paren(0, (*m_presult)[0]);
 481          m_presult->set_first(position, 0, true);
 482          pstate = pstate->next.p;
 483          break;
 484       }
 485    default:
 486    {
 487       BOOST_ASSERT(index > 0);
 488       if((m_match_flags & match_nosubs) == 0)
 489       {
 490          push_matched_paren(index, (*m_presult)[index]);
 491          m_presult->set_first(position, index);
 492       }
 493       pstate = pstate->next.p;
 494       break;
 495    }
 496    }
 497    return true;
 498 }
 499
 500 template <class BidiIterator, class Allocator, class traits>
 501 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
 502 {
 503    bool take_first, take_second;
 504    const re_alt* jmp = static_cast<const re_alt*>(pstate);
 505
 506    // find out which of these two alternatives we need to take:
 507    if(position == last)
 508    {
 509       take_first = jmp->can_be_null & mask_take;
 510       take_second = jmp->can_be_null & mask_skip;
 511    }
 512    else
 513    {
 514       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
 515       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
 516   }
 517
 518    if(take_first)
 519    {
 520       // we can take the first alternative,
 521       // see if we need to push next alternative:
 522       if(take_second)
 523       {
 524          push_alt(jmp->alt.p);
 525       }
 526       pstate = pstate->next.p;
 527       return true;
 528    }
 529    if(take_second)
 530    {
 531       pstate = jmp->alt.p;
 532       return true;
 533    }
 534    return false;  // neither option is possible
 535 }
 536
 537 template <class BidiIterator, class Allocator, class traits>
 538 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
 539 {
 540 #ifdef BOOST_MSVC
 541 #pragma warning(push)
 542 #pragma warning(disable:4127 4244)
 543 #endif
 544 #ifdef __BORLANDC__
 545 #pragma option push -w-8008 -w-8066 -w-8004
 546 #endif
 547    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 548
 549    // find out which of these two alternatives we need to take:
 550    bool take_first, take_second;
 551    if(position == last)
 552    {
 553       take_first = rep->can_be_null & mask_take;
 554       take_second = rep->can_be_null & mask_skip;
 555    }
 556    else
 557    {
 558       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
 559       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
 560    }
 561
 562    if((m_backup_state->state_id != saved_state_repeater_count)
 563       || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
 564       || (next_count->get_id() != rep->state_id))
 565    {
 566       // we're moving to a different repeat from the last
 567       // one, so set up a counter object:
 568       push_repeater_count(rep->state_id, &next_count);
 569    }
 570    //
 571    // If we've had at least one repeat already, and the last one
 572    // matched the NULL string then set the repeat count to
 573    // maximum:
 574    //
 575    next_count->check_null_repeat(position, rep->max);
 576
 577    if(next_count->get_count() < rep->min)
 578    {
 579       // we must take the repeat:
 580       if(take_first)
 581       {
 582          // increase the counter:
 583          ++(*next_count);
 584          pstate = rep->next.p;
 585          return true;
 586       }
 587       return false;
 588    }
 589
 590    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 591    if(greedy)
 592    {
 593       // try and take the repeat if we can:
 594       if((next_count->get_count() < rep->max) && take_first)
 595       {
 596          if(take_second)
 597          {
 598             // store position in case we fail:
 599             push_alt(rep->alt.p);
 600          }
 601          // increase the counter:
 602          ++(*next_count);
 603          pstate = rep->next.p;
 604          return true;
 605       }
 606       else if(take_second)
 607       {
 608          pstate = rep->alt.p;
 609          return true;
 610       }
 611       return false; // can't take anything, fail...
 612    }
 613    else // non-greedy
 614    {
 615       // try and skip the repeat if we can:
 616       if(take_second)
 617       {
 618          if((next_count->get_count() < rep->max) && take_first)
 619          {
 620             // store position in case we fail:
 621             push_non_greedy_repeat(rep->next.p);
 622          }
 623          pstate = rep->alt.p;
 624          return true;
 625       }
 626       if((next_count->get_count() < rep->max) && take_first)
 627       {
 628          // increase the counter:
 629          ++(*next_count);
 630          pstate = rep->next.p;
 631          return true;
 632       }
 633    }
 634    return false;
 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>
 644 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 645 {
 646    unsigned count = 0;
 647    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 648    re_syntax_base* psingle = rep->next.p;
 649    // match compulsary repeats first:
 650    while(count < rep->min)
 651    {
 652       pstate = psingle;
 653       if(!match_wild())
 654          return false;
 655       ++count;
 656    }
 657    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 658    if(greedy)
 659    {
 660       // repeat for as long as we can:
 661       while(count < rep->max)
 662       {
 663          pstate = psingle;
 664          if(!match_wild())
 665             break;
 666          ++count;
 667       }
 668       // remember where we got to if this is a leading repeat:
 669       if((rep->leading) && (count < rep->max))
 670          restart = position;
 671       // push backtrack info if available:
 672       if(count - rep->min)
 673          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 674       // jump to next state:
 675       pstate = rep->alt.p;
 676       return true;
 677    }
 678    else
 679    {
 680       // non-greedy, push state and return true if we can skip:
 681       if(count < rep->max)
 682          push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
 683       pstate = rep->alt.p;
 684       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 685    }
 686 }
 687
 688 template <class BidiIterator, class Allocator, class traits>
 689 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 690 {
 691    if(m_match_flags & match_not_dot_null)
 692       return match_dot_repeat_slow();
 693    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 694       return match_dot_repeat_slow();
 695
 696    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 697    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 698    unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::BOOST_REGEX_DETAIL_NS::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));
 699    if(rep->min > count)
 700    {
 701       position = last;
 702       return false;  // not enough text left to match
 703    }
 704    std::advance(position, count);
 705
 706    if(greedy)
 707    {
 708       if((rep->leading) && (count < rep->max))
 709          restart = position;
 710       // push backtrack info if available:
 711       if(count - rep->min)
 712          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 713       // jump to next state:
 714       pstate = rep->alt.p;
 715       return true;
 716    }
 717    else
 718    {
 719       // non-greedy, push state and return true if we can skip:
 720       if(count < rep->max)
 721          push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
 722       pstate = rep->alt.p;
 723       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 724    }
 725 }
 726
 727 template <class BidiIterator, class Allocator, class traits>
 728 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 729 {
 730 #ifdef BOOST_MSVC
 731 #pragma warning(push)
 732 #pragma warning(disable:4127)
 733 #endif
 734 #ifdef __BORLANDC__
 735 #pragma option push -w-8008 -w-8066 -w-8004
 736 #endif
 737    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 738    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 739    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 740    std::size_t count = 0;
 741    //
 742    // start by working out how much we can skip:
 743    //
 744    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 745    std::size_t desired = greedy ? rep->max : rep->min;
 746    if(::boost::is_random_access_iterator<BidiIterator>::value)
 747    {
 748       BidiIterator end = position;
 749       // Move end forward by "desired", preferably without using distance or advance if we can
 750       // as these can be slow for some iterator types.
 751       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
 752       if(desired >= len)
 753          end = last;
 754       else
 755          std::advance(end, desired);
 756       BidiIterator origin(position);
 757       while((position != end) && (traits_inst.translate(*position, icase) == what))
 758       {
 759          ++position;
 760       }
 761       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
 762    }
 763    else
 764    {
 765       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 766       {
 767          ++position;
 768          ++count;
 769       }
 770    }
 771
 772    if(count < rep->min)
 773       return false;
 774
 775    if(greedy)
 776    {
 777       if((rep->leading) && (count < rep->max))
 778          restart = position;
 779       // push backtrack info if available:
 780       if(count - rep->min)
 781          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 782       // jump to next state:
 783       pstate = rep->alt.p;
 784       return true;
 785    }
 786    else
 787    {
 788       // non-greedy, push state and return true if we can skip:
 789       if(count < rep->max)
 790          push_single_repeat(count, rep, position, saved_state_rep_char);
 791       pstate = rep->alt.p;
 792       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 793    }
 794 #ifdef __BORLANDC__
 795 #pragma option pop
 796 #endif
 797 #ifdef BOOST_MSVC
 798 #pragma warning(pop)
 799 #endif
 800 }
 801
 802 template <class BidiIterator, class Allocator, class traits>
 803 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 804 {
 805 #ifdef BOOST_MSVC
 806 #pragma warning(push)
 807 #pragma warning(disable:4127)
 808 #endif
 809 #ifdef __BORLANDC__
 810 #pragma option push -w-8008 -w-8066 -w-8004
 811 #endif
 812    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 813    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 814    std::size_t count = 0;
 815    //
 816    // start by working out how much we can skip:
 817    //
 818    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 819    std::size_t desired = greedy ? rep->max : rep->min;
 820    if(::boost::is_random_access_iterator<BidiIterator>::value)
 821    {
 822       BidiIterator end = position;
 823       // Move end forward by "desired", preferably without using distance or advance if we can
 824       // as these can be slow for some iterator types.
 825       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
 826       if(desired >= len)
 827          end = last;
 828       else
 829          std::advance(end, desired);
 830       BidiIterator origin(position);
 831       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 832       {
 833          ++position;
 834       }
 835       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
 836    }
 837    else
 838    {
 839       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 840       {
 841          ++position;
 842          ++count;
 843       }
 844    }
 845
 846    if(count < rep->min)
 847       return false;
 848
 849    if(greedy)
 850    {
 851       if((rep->leading) && (count < rep->max))
 852          restart = position;
 853       // push backtrack info if available:
 854       if(count - rep->min)
 855          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 856       // jump to next state:
 857       pstate = rep->alt.p;
 858       return true;
 859    }
 860    else
 861    {
 862       // non-greedy, push state and return true if we can skip:
 863       if(count < rep->max)
 864          push_single_repeat(count, rep, position, saved_state_rep_short_set);
 865       pstate = rep->alt.p;
 866       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 867    }
 868 #ifdef __BORLANDC__
 869 #pragma option pop
 870 #endif
 871 #ifdef BOOST_MSVC
 872 #pragma warning(pop)
 873 #endif
 874 }
 875
 876 template <class BidiIterator, class Allocator, class traits>
 877 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 878 {
 879 #ifdef BOOST_MSVC
 880 #pragma warning(push)
 881 #pragma warning(disable:4127)
 882 #endif
 883 #ifdef __BORLANDC__
 884 #pragma option push -w-8008 -w-8066 -w-8004
 885 #endif
 886    typedef typename traits::char_class_type m_type;
 887    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 888    const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate->next.p);
 889    std::size_t count = 0;
 890    //
 891    // start by working out how much we can skip:
 892    //
 893    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 894    std::size_t desired = greedy ? rep->max : rep->min;
 895    if(::boost::is_random_access_iterator<BidiIterator>::value)
 896    {
 897       BidiIterator end = position;
 898       // Move end forward by "desired", preferably without using distance or advance if we can
 899       // as these can be slow for some iterator types.
 900       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
 901       if(desired >= len)
 902          end = last;
 903       else
 904          std::advance(end, desired);
 905       BidiIterator origin(position);
 906       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 907       {
 908          ++position;
 909       }
 910       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
 911    }
 912    else
 913    {
 914       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 915       {
 916          ++position;
 917          ++count;
 918       }
 919    }
 920
 921    if(count < rep->min)
 922       return false;
 923
 924    if(greedy)
 925    {
 926       if((rep->leading) && (count < rep->max))
 927          restart = position;
 928       // push backtrack info if available:
 929       if(count - rep->min)
 930          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
 931       // jump to next state:
 932       pstate = rep->alt.p;
 933       return true;
 934    }
 935    else
 936    {
 937       // non-greedy, push state and return true if we can skip:
 938       if(count < rep->max)
 939          push_single_repeat(count, rep, position, saved_state_rep_long_set);
 940       pstate = rep->alt.p;
 941       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
 942    }
 943 #ifdef __BORLANDC__
 944 #pragma option pop
 945 #endif
 946 #ifdef BOOST_MSVC
 947 #pragma warning(pop)
 948 #endif
 949 }
 950
 951 template <class BidiIterator, class Allocator, class traits>
 952 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
 953 {
 954    BOOST_ASSERT(pstate->type == syntax_element_recurse);
 955    //
 956    // Backup call stack:
 957    //
 958    push_recursion_pop();
 959    //
 960    // Set new call stack:
 961    //
 962    if(recursion_stack.capacity() == 0)
 963    {
 964       recursion_stack.reserve(50);
 965    }
 966    recursion_stack.push_back(recursion_info<results_type>());
 967    recursion_stack.back().preturn_address = pstate->next.p;
 968    recursion_stack.back().results = *m_presult;
 969    pstate = static_cast<const re_jump*>(pstate)->alt.p;
 970    recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
 971    //if(static_cast<const re_recurse*>(pstate)->state_id > 0)
 972    {
 973       push_repeater_count(-(2 + static_cast<const re_brace*>(pstate)->index), &next_count);
 974    }
 975
 976    return true;
 977 }
 978
 979 template <class BidiIterator, class Allocator, class traits>
 980 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
 981 {
 982    int index = static_cast<const re_brace*>(pstate)->index;
 983    icase = static_cast<const re_brace*>(pstate)->icase;
 984    if(index > 0)
 985    {
 986       if((m_match_flags & match_nosubs) == 0)
 987       {
 988          m_presult->set_second(position, index);
 989       }
 990       if(!recursion_stack.empty())
 991       {
 992          if(index == recursion_stack.back().idx)
 993          {
 994             pstate = recursion_stack.back().preturn_address;
 995             *m_presult = recursion_stack.back().results;
 996             push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, &recursion_stack.back().results);
 997             recursion_stack.pop_back();
 998             push_repeater_count(-(2 + index), &next_count);
 999          }
1000       }
1001    }
1002    else if((index < 0) && (index != -4))
1003    {
1004       // matched forward lookahead:
1005       pstate = 0;
1006       return true;
1007    }
1008    pstate = pstate->next.p;
1009    return true;
1010 }
1011
1012 template <class BidiIterator, class Allocator, class traits>
1013 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
1014 {
1015    if(!recursion_stack.empty())
1016    {
1017       BOOST_ASSERT(0 == recursion_stack.back().idx);
1018       pstate = recursion_stack.back().preturn_address;
1019       *m_presult = recursion_stack.back().results;
1020       push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, &recursion_stack.back().results);
1021       recursion_stack.pop_back();
1022       return true;
1023    }
1024    if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
1025       return false;
1026    if((m_match_flags & match_all) && (position != last))
1027       return false;
1028    if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
1029       return false;
1030    m_presult->set_second(position);
1031    pstate = 0;
1032    m_has_found_match = true;
1033    if((m_match_flags & match_posix) == match_posix)
1034    {
1035       m_result.maybe_assign(*m_presult);
1036       if((m_match_flags & match_any) == 0)
1037          return false;
1038    }
1039 #ifdef BOOST_REGEX_MATCH_EXTRA
1040    if(match_extra & m_match_flags)
1041    {
1042       for(unsigned i = 0; i < m_presult->size(); ++i)
1043          if((*m_presult)[i].matched)
1044             ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
1045    }
1046 #endif
1047    return true;
1048 }
1049
1050 template <class BidiIterator, class Allocator, class traits>
1051 bool perl_matcher<BidiIterator, Allocator, traits>::match_commit()
1052 {
1053    // Ideally we would just junk all the states that are on the stack,
1054    // however we might not unwind correctly in that case, so for now,
1055    // just mark that we don't backtrack into whatever is left (or rather
1056    // we'll unwind it unconditionally without pausing to try other matches).
1057
1058    switch(static_cast<const re_commit*>(pstate)->action)
1059    {
1060    case commit_commit:
1061       restart = last;
1062       break;
1063    case commit_skip:
1064       if(base != position)
1065       {
1066          restart = position;
1067          // Have to decrement restart since it will get incremented again later:
1068          --restart;
1069       }
1070       break;
1071    case commit_prune:
1072       break;
1073    }
1074
1075    saved_state* pmp = m_backup_state;
1076    --pmp;
1077    if(pmp < m_stack_base)
1078    {
1079       extend_stack();
1080       pmp = m_backup_state;
1081       --pmp;
1082    }
1083    (void) new (pmp)saved_state(16);
1084    m_backup_state = pmp;
1085    pstate = pstate->next.p;
1086    return true;
1087 }
1088
1089 template <class BidiIterator, class Allocator, class traits>
1090 bool perl_matcher<BidiIterator, Allocator, traits>::match_then()
1091 {
1092    // Just leave a mark that we need to skip to next alternative:
1093    saved_state* pmp = m_backup_state;
1094    --pmp;
1095    if(pmp < m_stack_base)
1096    {
1097       extend_stack();
1098       pmp = m_backup_state;
1099       --pmp;
1100    }
1101    (void) new (pmp)saved_state(17);
1102    m_backup_state = pmp;
1103    pstate = pstate->next.p;
1104    return true;
1105 }
1106
1107 template <class BidiIterator, class Allocator, class traits>
1108 bool perl_matcher<BidiIterator, Allocator, traits>::skip_until_paren(int index, bool have_match)
1109 {
1110    while(pstate)
1111    {
1112       if(pstate->type == syntax_element_endmark)
1113       {
1114          if(static_cast<const re_brace*>(pstate)->index == index)
1115          {
1116             if(have_match)
1117                return this->match_endmark();
1118             pstate = pstate->next.p;
1119             return true;
1120          }
1121          else
1122          {
1123             // Unenclosed closing ), occurs when (*ACCEPT) is inside some other
1124             // parenthesis which may or may not have other side effects associated with it.
1125             match_endmark();
1126             if(!pstate)
1127             {
1128                unwind(true);
1129             }
1130          }
1131          continue;
1132       }
1133       else if(pstate->type == syntax_element_match)
1134          return true;
1135       else if(pstate->type == syntax_element_startmark)
1136       {
1137          int idx = static_cast<const re_brace*>(pstate)->index;
1138          pstate = pstate->next.p;
1139          skip_until_paren(idx, false);
1140          continue;
1141       }
1142       pstate = pstate->next.p;
1143    }
1144    return true;
1145 }
1146
1147 /****************************************************************************
1148
1149 Unwind and associated proceedures follow, these perform what normal stack
1150 unwinding does in the recursive implementation.
1151
1152 ****************************************************************************/
1153
1154 template <class BidiIterator, class Allocator, class traits>
1155 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
1156 {
1157    static unwind_proc_type const s_unwind_table[19] =
1158    {
1159       &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
1160       &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
1161       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
1162       &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
1163       &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
1164       &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
1165       &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
1166       &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
1167       &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
1168       &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
1169       &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
1170       &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
1171       &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
1172       &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
1173       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion,
1174       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop,
1175       &perl_matcher<BidiIterator, Allocator, traits>::unwind_commit,
1176       &perl_matcher<BidiIterator, Allocator, traits>::unwind_then,
1177       &perl_matcher<BidiIterator, Allocator, traits>::unwind_case,
1178    };
1179
1180    m_recursive_result = have_match;
1181    m_unwound_lookahead = false;
1182    m_unwound_alt = false;
1183    unwind_proc_type unwinder;
1184    bool cont;
1185    //
1186    // keep unwinding our stack until we have something to do:
1187    //
1188    do
1189    {
1190       unwinder = s_unwind_table[m_backup_state->state_id];
1191       cont = (this->*unwinder)(m_recursive_result);
1192    }while(cont);
1193    //
1194    // return true if we have more states to try:
1195    //
1196    return pstate ? true : false;
1197 }
1198
1199 template <class BidiIterator, class Allocator, class traits>
1200 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
1201 {
1202    pstate = 0;   // nothing left to search
1203    return false; // end of stack nothing more to search
1204 }
1205
1206 template <class BidiIterator, class Allocator, class traits>
1207 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_case(bool)
1208 {
1209    saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
1210    icase = pmp->icase;
1211    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1212    m_backup_state = pmp;
1213    return true;
1214 }
1215
1216 template <class BidiIterator, class Allocator, class traits>
1217 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
1218 {
1219    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
1220    // restore previous values if no match was found:
1221    if(have_match == false)
1222    {
1223       m_presult->set_first(pmp->sub.first, pmp->index, pmp->index == 0);
1224       m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched, pmp->index == 0);
1225    }
1226 #ifdef BOOST_REGEX_MATCH_EXTRA
1227    //
1228    // we have a match, push the capture information onto the stack:
1229    //
1230    else if(pmp->sub.matched && (match_extra & m_match_flags))
1231       ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
1232 #endif
1233    // unwind stack:
1234    m_backup_state = pmp+1;
1235    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1236    return true; // keep looking
1237 }
1238
1239 template <class BidiIterator, class Allocator, class traits>
1240 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
1241 {
1242    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1243    pstate = 0;   // nothing left to search
1244    return false; // end of stack nothing more to search
1245 }
1246
1247 template <class BidiIterator, class Allocator, class traits>
1248 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
1249 {
1250    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
1251    pstate = pmp->pstate;
1252    position = pmp->position;
1253    bool result = (r == pmp->positive);
1254    m_recursive_result = pmp->positive ? r : !r;
1255    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1256    m_backup_state = pmp;
1257    m_unwound_lookahead = true;
1258    return !result; // return false if the assertion was matched to stop search.
1259 }
1260
1261 template <class BidiIterator, class Allocator, class traits>
1262 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
1263 {
1264    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1265    if(!r)
1266    {
1267       pstate = pmp->pstate;
1268       position = pmp->position;
1269    }
1270    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1271    m_backup_state = pmp;
1272    m_unwound_alt = !r;
1273    return r;
1274 }
1275
1276 template <class BidiIterator, class Allocator, class traits>
1277 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
1278 {
1279    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
1280    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1281    m_backup_state = pmp;
1282    return true; // keep looking
1283 }
1284
1285 template <class BidiIterator, class Allocator, class traits>
1286 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
1287 {
1288    saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
1289    void* condemmed = m_stack_base;
1290    m_stack_base = pmp->base;
1291    m_backup_state = pmp->end;
1292    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1293    put_mem_block(condemmed);
1294    return true; // keep looking
1295 }
1296
1297 template <class BidiIterator, class Allocator, class traits>
1298 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
1299 {
1300    saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1301    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(p++);
1302    m_backup_state = p;
1303 }
1304
1305 template <class BidiIterator, class Allocator, class traits>
1306 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
1307 {
1308    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1309
1310    // if we have a match, just discard this state:
1311    if(r)
1312    {
1313       destroy_single_repeat();
1314       return true;
1315    }
1316
1317    const re_repeat* rep = pmp->rep;
1318    std::size_t count = pmp->count;
1319    BOOST_ASSERT(rep->next.p != 0);
1320    BOOST_ASSERT(rep->alt.p != 0);
1321
1322    count -= rep->min;
1323
1324    if((m_match_flags & match_partial) && (position == last))
1325       m_has_partial_match = true;
1326
1327    BOOST_ASSERT(count);
1328    position = pmp->last_position;
1329
1330    // backtrack till we can skip out:
1331    do
1332    {
1333       --position;
1334       --count;
1335       ++state_count;
1336    }while(count && !can_start(*position, rep->_map, mask_skip));
1337
1338    // if we've hit base, destroy this state:
1339    if(count == 0)
1340    {
1341          destroy_single_repeat();
1342          if(!can_start(*position, rep->_map, mask_skip))
1343             return true;
1344    }
1345    else
1346    {
1347       pmp->count = count + rep->min;
1348       pmp->last_position = position;
1349    }
1350    pstate = rep->alt.p;
1351    return false;
1352 }
1353
1354 template <class BidiIterator, class Allocator, class traits>
1355 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1356 {
1357    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1358
1359    // if we have a match, just discard this state:
1360    if(r)
1361    {
1362       destroy_single_repeat();
1363       return true;
1364    }
1365
1366    const re_repeat* rep = pmp->rep;
1367    std::size_t count = pmp->count;
1368    BOOST_ASSERT(rep->type == syntax_element_dot_rep);
1369    BOOST_ASSERT(rep->next.p != 0);
1370    BOOST_ASSERT(rep->alt.p != 0);
1371    BOOST_ASSERT(rep->next.p->type == syntax_element_wild);
1372
1373    BOOST_ASSERT(count < rep->max);
1374    pstate = rep->next.p;
1375    position = pmp->last_position;
1376
1377    if(position != last)
1378    {
1379       // wind forward until we can skip out of the repeat:
1380       do
1381       {
1382          if(!match_wild())
1383          {
1384             // failed repeat match, discard this state and look for another:
1385             destroy_single_repeat();
1386             return true;
1387          }
1388          ++count;
1389          ++state_count;
1390          pstate = rep->next.p;
1391       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1392    }
1393    if(position == last)
1394    {
1395       // can't repeat any more, remove the pushed state:
1396       destroy_single_repeat();
1397       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1398          m_has_partial_match = true;
1399       if(0 == (rep->can_be_null & mask_skip))
1400          return true;
1401    }
1402    else if(count == rep->max)
1403    {
1404       // can't repeat any more, remove the pushed state:
1405       destroy_single_repeat();
1406       if(!can_start(*position, rep->_map, mask_skip))
1407          return true;
1408    }
1409    else
1410    {
1411       pmp->count = count;
1412       pmp->last_position = position;
1413    }
1414    pstate = rep->alt.p;
1415    return false;
1416 }
1417
1418 template <class BidiIterator, class Allocator, class traits>
1419 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1420 {
1421    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1422
1423    // if we have a match, just discard this state:
1424    if(r)
1425    {
1426       destroy_single_repeat();
1427       return true;
1428    }
1429
1430    const re_repeat* rep = pmp->rep;
1431    std::size_t count = pmp->count;
1432
1433    BOOST_ASSERT(count < rep->max);
1434    position = pmp->last_position;
1435    if(position != last)
1436    {
1437
1438       // wind forward until we can skip out of the repeat:
1439       do
1440       {
1441          ++position;
1442          ++count;
1443          ++state_count;
1444       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1445    }
1446
1447    // remember where we got to if this is a leading repeat:
1448    if((rep->leading) && (count < rep->max))
1449       restart = position;
1450    if(position == last)
1451    {
1452       // can't repeat any more, remove the pushed state:
1453       destroy_single_repeat();
1454       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1455          m_has_partial_match = true;
1456       if(0 == (rep->can_be_null & mask_skip))
1457          return true;
1458    }
1459    else if(count == rep->max)
1460    {
1461       // can't repeat any more, remove the pushed state:
1462       destroy_single_repeat();
1463       if(!can_start(*position, rep->_map, mask_skip))
1464          return true;
1465    }
1466    else
1467    {
1468       pmp->count = count;
1469       pmp->last_position = position;
1470    }
1471    pstate = rep->alt.p;
1472    return false;
1473 }
1474
1475 template <class BidiIterator, class Allocator, class traits>
1476 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1477 {
1478    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1479
1480    // if we have a match, just discard this state:
1481    if(r)
1482    {
1483       destroy_single_repeat();
1484       return true;
1485    }
1486
1487    const re_repeat* rep = pmp->rep;
1488    std::size_t count = pmp->count;
1489    pstate = rep->next.p;
1490    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
1491    position = pmp->last_position;
1492
1493    BOOST_ASSERT(rep->type == syntax_element_char_rep);
1494    BOOST_ASSERT(rep->next.p != 0);
1495    BOOST_ASSERT(rep->alt.p != 0);
1496    BOOST_ASSERT(rep->next.p->type == syntax_element_literal);
1497    BOOST_ASSERT(count < rep->max);
1498
1499    if(position != last)
1500    {
1501       // wind forward until we can skip out of the repeat:
1502       do
1503       {
1504          if(traits_inst.translate(*position, icase) != what)
1505          {
1506             // failed repeat match, discard this state and look for another:
1507             destroy_single_repeat();
1508             return true;
1509          }
1510          ++count;
1511          ++ position;
1512          ++state_count;
1513          pstate = rep->next.p;
1514       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1515    }
1516    // remember where we got to if this is a leading repeat:
1517    if((rep->leading) && (count < rep->max))
1518       restart = position;
1519    if(position == last)
1520    {
1521       // can't repeat any more, remove the pushed state:
1522       destroy_single_repeat();
1523       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1524          m_has_partial_match = true;
1525       if(0 == (rep->can_be_null & mask_skip))
1526          return true;
1527    }
1528    else if(count == rep->max)
1529    {
1530       // can't repeat any more, remove the pushed state:
1531       destroy_single_repeat();
1532       if(!can_start(*position, rep->_map, mask_skip))
1533          return true;
1534    }
1535    else
1536    {
1537       pmp->count = count;
1538       pmp->last_position = position;
1539    }
1540    pstate = rep->alt.p;
1541    return false;
1542 }
1543
1544 template <class BidiIterator, class Allocator, class traits>
1545 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1546 {
1547    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1548
1549    // if we have a match, just discard this state:
1550    if(r)
1551    {
1552       destroy_single_repeat();
1553       return true;
1554    }
1555
1556    const re_repeat* rep = pmp->rep;
1557    std::size_t count = pmp->count;
1558    pstate = rep->next.p;
1559    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1560    position = pmp->last_position;
1561
1562    BOOST_ASSERT(rep->type == syntax_element_short_set_rep);
1563    BOOST_ASSERT(rep->next.p != 0);
1564    BOOST_ASSERT(rep->alt.p != 0);
1565    BOOST_ASSERT(rep->next.p->type == syntax_element_set);
1566    BOOST_ASSERT(count < rep->max);
1567
1568    if(position != last)
1569    {
1570       // wind forward until we can skip out of the repeat:
1571       do
1572       {
1573          if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1574          {
1575             // failed repeat match, discard this state and look for another:
1576             destroy_single_repeat();
1577             return true;
1578          }
1579          ++count;
1580          ++ position;
1581          ++state_count;
1582          pstate = rep->next.p;
1583       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1584    }
1585    // remember where we got to if this is a leading repeat:
1586    if((rep->leading) && (count < rep->max))
1587       restart = position;
1588    if(position == last)
1589    {
1590       // can't repeat any more, remove the pushed state:
1591       destroy_single_repeat();
1592       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1593          m_has_partial_match = true;
1594       if(0 == (rep->can_be_null & mask_skip))
1595          return true;
1596    }
1597    else if(count == rep->max)
1598    {
1599       // can't repeat any more, remove the pushed state:
1600       destroy_single_repeat();
1601       if(!can_start(*position, rep->_map, mask_skip))
1602          return true;
1603    }
1604    else
1605    {
1606       pmp->count = count;
1607       pmp->last_position = position;
1608    }
1609    pstate = rep->alt.p;
1610    return false;
1611 }
1612
1613 template <class BidiIterator, class Allocator, class traits>
1614 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1615 {
1616    typedef typename traits::char_class_type m_type;
1617    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1618
1619    // if we have a match, just discard this state:
1620    if(r)
1621    {
1622       destroy_single_repeat();
1623       return true;
1624    }
1625
1626    const re_repeat* rep = pmp->rep;
1627    std::size_t count = pmp->count;
1628    pstate = rep->next.p;
1629    const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate);
1630    position = pmp->last_position;
1631
1632    BOOST_ASSERT(rep->type == syntax_element_long_set_rep);
1633    BOOST_ASSERT(rep->next.p != 0);
1634    BOOST_ASSERT(rep->alt.p != 0);
1635    BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1636    BOOST_ASSERT(count < rep->max);
1637
1638    if(position != last)
1639    {
1640       // wind forward until we can skip out of the repeat:
1641       do
1642       {
1643          if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1644          {
1645             // failed repeat match, discard this state and look for another:
1646             destroy_single_repeat();
1647             return true;
1648          }
1649          ++position;
1650          ++count;
1651          ++state_count;
1652          pstate = rep->next.p;
1653       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1654    }
1655    // remember where we got to if this is a leading repeat:
1656    if((rep->leading) && (count < rep->max))
1657       restart = position;
1658    if(position == last)
1659    {
1660       // can't repeat any more, remove the pushed state:
1661       destroy_single_repeat();
1662       if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1663          m_has_partial_match = true;
1664       if(0 == (rep->can_be_null & mask_skip))
1665          return true;
1666    }
1667    else if(count == rep->max)
1668    {
1669       // can't repeat any more, remove the pushed state:
1670       destroy_single_repeat();
1671       if(!can_start(*position, rep->_map, mask_skip))
1672          return true;
1673    }
1674    else
1675    {
1676       pmp->count = count;
1677       pmp->last_position = position;
1678    }
1679    pstate = rep->alt.p;
1680    return false;
1681 }
1682
1683 template <class BidiIterator, class Allocator, class traits>
1684 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1685 {
1686    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1687    if(!r)
1688    {
1689       position = pmp->position;
1690       pstate = pmp->pstate;
1691       ++(*next_count);
1692    }
1693    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1694    m_backup_state = pmp;
1695    return r;
1696 }
1697
1698 template <class BidiIterator, class Allocator, class traits>
1699 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion(bool r)
1700 {
1701    saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
1702    if(!r)
1703    {
1704       recursion_stack.push_back(recursion_info<results_type>());
1705       recursion_stack.back().idx = pmp->recursion_id;
1706       recursion_stack.back().preturn_address = pmp->preturn_address;
1707       recursion_stack.back().results = pmp->results;
1708    }
1709    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1710    m_backup_state = pmp;
1711    return true;
1712 }
1713
1714 template <class BidiIterator, class Allocator, class traits>
1715 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop(bool r)
1716 {
1717    saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1718    if(!r)
1719    {
1720       recursion_stack.pop_back();
1721    }
1722    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1723    m_backup_state = pmp;
1724    return true;
1725 }
1726
1727 template <class BidiIterator, class Allocator, class traits>
1728 void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_pop()
1729 {
1730    saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1731    --pmp;
1732    if(pmp < m_stack_base)
1733    {
1734       extend_stack();
1735       pmp = static_cast<saved_state*>(m_backup_state);
1736       --pmp;
1737    }
1738    (void) new (pmp)saved_state(15);
1739    m_backup_state = pmp;
1740 }
1741
1742 template <class BidiIterator, class Allocator, class traits>
1743 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_commit(bool b)
1744 {
1745    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1746    while(unwind(b) && !m_unwound_lookahead){}
1747    if(m_unwound_lookahead && pstate)
1748    {
1749       //
1750       // If we stop because we just unwound an assertion, put the
1751       // commit state back on the stack again:
1752       //
1753       saved_state* pmp = m_backup_state;
1754       --pmp;
1755       if(pmp < m_stack_base)
1756       {
1757          extend_stack();
1758          pmp = m_backup_state;
1759          --pmp;
1760       }
1761       (void) new (pmp)saved_state(16);
1762       m_backup_state = pmp;
1763    }
1764    // This prevents us from stopping when we exit from an independent sub-expression:
1765    m_independent = false;
1766    return false;
1767 }
1768
1769 template <class BidiIterator, class Allocator, class traits>
1770 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_then(bool b)
1771 {
1772    // Unwind everything till we hit an alternative:
1773    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1774    bool result = false;
1775    while((result = unwind(b)) && !m_unwound_alt){}
1776    // We're now pointing at the next alternative, need one more backtrack
1777    // since *all* the other alternatives must fail once we've reached a THEN clause:
1778    if(result && m_unwound_alt)
1779       unwind(b);
1780    return false;
1781 }
1782
1783 /*
1784 template <class BidiIterator, class Allocator, class traits>
1785 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_pop(bool r)
1786 {
1787    saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1788    if(!r)
1789    {
1790       --parenthesis_stack_position;
1791    }
1792    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1793    m_backup_state = pmp;
1794    return true;
1795 }
1796
1797 template <class BidiIterator, class Allocator, class traits>
1798 void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_pop()
1799 {
1800    saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1801    --pmp;
1802    if(pmp < m_stack_base)
1803    {
1804       extend_stack();
1805       pmp = static_cast<saved_state*>(m_backup_state);
1806       --pmp;
1807    }
1808    (void) new (pmp)saved_state(16);
1809    m_backup_state = pmp;
1810 }
1811
1812 template <class BidiIterator, class Allocator, class traits>
1813 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_parenthesis_push(bool r)
1814 {
1815    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1816    if(!r)
1817    {
1818       parenthesis_stack[parenthesis_stack_position++] = pmp->position;
1819    }
1820    boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1821    m_backup_state = pmp;
1822    return true;
1823 }
1824
1825 template <class BidiIterator, class Allocator, class traits>
1826 inline void perl_matcher<BidiIterator, Allocator, traits>::push_parenthesis_push(BidiIterator p)
1827 {
1828    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1829    --pmp;
1830    if(pmp < m_stack_base)
1831    {
1832       extend_stack();
1833       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1834       --pmp;
1835    }
1836    (void) new (pmp)saved_position<BidiIterator>(0, p, 17);
1837    m_backup_state = pmp;
1838 }
1839 */
1840 } // namespace BOOST_REGEX_DETAIL_NS
1841 } // namespace boost
1842
1843 #ifdef BOOST_MSVC
1844 #  pragma warning(pop)
1845 #endif
1846
1847 #ifdef BOOST_MSVC
1848 #pragma warning(push)
1849 #pragma warning(disable: 4103)
1850 #endif
1851 #ifdef BOOST_HAS_ABI_HEADERS
1852 #  include BOOST_ABI_SUFFIX
1853 #endif
1854 #ifdef BOOST_MSVC
1855 #pragma warning(pop)
1856 #endif
1857
1858 #endif
1859
1860