3rdparty/boost/boost/regex/v4/perl_matcher_non_recursive.hpp

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