3rdparty/boost/boost/regex/v4/perl_matcher_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 recursive implementation.
  18   */
  19
  20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
  21 #define BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
  22
  23 #ifdef BOOST_MSVC
  24 #pragma warning(push)
  25 #pragma warning(disable: 4103)
  26 #endif
  27 #ifdef BOOST_HAS_ABI_HEADERS
  28 #  include BOOST_ABI_PREFIX
  29 #endif
  30 #ifdef BOOST_MSVC
  31 #pragma warning(pop)
  32 #endif
  33
  34 #ifdef BOOST_MSVC
  35 #pragma warning(push)
  36 #pragma warning(disable: 4800)
  37 #endif
  38
  39 namespace boost{
  40 namespace BOOST_REGEX_DETAIL_NS{
  41
  42 template <class BidiIterator>
  43 class backup_subex
  44 {
  45    int index;
  46    sub_match<BidiIterator> sub;
  47 public:
  48    template <class A>
  49    backup_subex(const match_results<BidiIterator, A>& w, int i)
  50       : index(i), sub(w[i], false) {}
  51    template <class A>
  52    void restore(match_results<BidiIterator, A>& w)
  53    {
  54       w.set_first(sub.first, index, index == 0);
  55       w.set_second(sub.second, index, sub.matched, index == 0);
  56    }
  57    const sub_match<BidiIterator>& get() { return sub; }
  58 };
  59
  60 template <class BidiIterator, class Allocator, class traits>
  61 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
  62 {
  63    static matcher_proc_type const s_match_vtable[34] =
  64    {
  65       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
  66       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
  67       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
  68       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
  69       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
  70       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
  71       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
  72       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
  73       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
  74       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
  75       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
  76       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
  77       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
  78       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
  79       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
  80       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
  81       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
  82       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
  83       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
  84       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
  85       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
  86       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
  87       // Although this next line *should* be evaluated at compile time, in practice
  88       // some compilers (VC++) emit run-time initialisation which breaks thread
  89       // safety, so use a dispatch function instead:
  90       //(::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),
  91       &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
  92       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
  93       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
  94       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
  95       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
  96       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
  97       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
  98       &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
  99       &perl_matcher<BidiIterator, Allocator, traits>::match_fail,
 100       &perl_matcher<BidiIterator, Allocator, traits>::match_accept,
 101       &perl_matcher<BidiIterator, Allocator, traits>::match_commit,
 102       &perl_matcher<BidiIterator, Allocator, traits>::match_then,
 103    };
 104
 105    if(state_count > max_state_count)
 106       raise_error(traits_inst, regex_constants::error_complexity);
 107    while(pstate)
 108    {
 109       matcher_proc_type proc = s_match_vtable[pstate->type];
 110       ++state_count;
 111       if(!(this->*proc)())
 112       {
 113          if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 114             m_has_partial_match = true;
 115          return 0;
 116       }
 117    }
 118    return true;
 119 }
 120
 121 template <class BidiIterator, class Allocator, class traits>
 122 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
 123 {
 124    int index = static_cast<const re_brace*>(pstate)->index;
 125    icase = static_cast<const re_brace*>(pstate)->icase;
 126    bool r = true;
 127    switch(index)
 128    {
 129    case 0:
 130       pstate = pstate->next.p;
 131       break;
 132    case -1:
 133    case -2:
 134       {
 135          // forward lookahead assert:
 136          BidiIterator old_position(position);
 137          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 138          pstate = pstate->next.p->next.p;
 139          r = match_all_states();
 140          pstate = next_pstate;
 141          position = old_position;
 142          if((r && (index != -1)) || (!r && (index != -2)))
 143             r = false;
 144          else
 145             r = true;
 146          if(r && m_have_accept)
 147             r = skip_until_paren(INT_MAX);
 148          break;
 149       }
 150    case -3:
 151       {
 152          // independent sub-expression:
 153          bool old_independent = m_independent;
 154          m_independent = true;
 155          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 156          pstate = pstate->next.p->next.p;
 157          bool can_backtrack = m_can_backtrack;
 158          r = match_all_states();
 159          if(r)
 160             m_can_backtrack = can_backtrack;
 161          pstate = next_pstate;
 162          m_independent = old_independent;
 163 #ifdef BOOST_REGEX_MATCH_EXTRA
 164          if(r && (m_match_flags & match_extra))
 165          {
 166             //
 167             // our captures have been stored in *m_presult
 168             // we need to unpack them, and insert them
 169             // back in the right order when we unwind the stack:
 170             //
 171             unsigned i;
 172             match_results<BidiIterator, Allocator> tm(*m_presult);
 173             for(i = 0; i < tm.size(); ++i)
 174                (*m_presult)[i].get_captures().clear();
 175             // match everything else:
 176             r = match_all_states();
 177             // now place the stored captures back:
 178             for(i = 0; i < tm.size(); ++i)
 179             {
 180                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
 181                seq& s1 = (*m_presult)[i].get_captures();
 182                const seq& s2 = tm[i].captures();
 183                s1.insert(
 184                   s1.end(),
 185                   s2.begin(),
 186                   s2.end());
 187             }
 188          }
 189 #endif
 190          if(r && m_have_accept)
 191             r = skip_until_paren(INT_MAX);
 192          break;
 193       }
 194    case -4:
 195       {
 196       // conditional expression:
 197       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
 198       BOOST_ASSERT(alt->type == syntax_element_alt);
 199       pstate = alt->next.p;
 200       if(pstate->type == syntax_element_assert_backref)
 201       {
 202          if(!match_assert_backref())
 203             pstate = alt->alt.p;
 204          break;
 205       }
 206       else
 207       {
 208          // zero width assertion, have to match this recursively:
 209          BOOST_ASSERT(pstate->type == syntax_element_startmark);
 210          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
 211          BidiIterator saved_position = position;
 212          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 213          pstate = pstate->next.p->next.p;
 214          bool res = match_all_states();
 215          position = saved_position;
 216          if(negated)
 217             res = !res;
 218          if(res)
 219             pstate = next_pstate;
 220          else
 221             pstate = alt->alt.p;
 222          break;
 223       }
 224       }
 225    case -5:
 226       {
 227          // Reset start of $0, since we have a \K escape
 228          backup_subex<BidiIterator> sub(*m_presult, 0);
 229          m_presult->set_first(position, 0, true);
 230          pstate = pstate->next.p;
 231          r = match_all_states();
 232          if(r == false)
 233             sub.restore(*m_presult);
 234          break;
 235       }
 236    default:
 237    {
 238       BOOST_ASSERT(index > 0);
 239       if((m_match_flags & match_nosubs) == 0)
 240       {
 241          backup_subex<BidiIterator> sub(*m_presult, index);
 242          m_presult->set_first(position, index);
 243          pstate = pstate->next.p;
 244          r = match_all_states();
 245          if(r == false)
 246             sub.restore(*m_presult);
 247 #ifdef BOOST_REGEX_MATCH_EXTRA
 248          //
 249          // we have a match, push the capture information onto the stack:
 250          //
 251          else if(sub.get().matched && (match_extra & m_match_flags))
 252             ((*m_presult)[index]).get_captures().push_back(sub.get());
 253 #endif
 254       }
 255       else
 256       {
 257          pstate = pstate->next.p;
 258       }
 259       break;
 260    }
 261    }
 262    return r;
 263 }
 264
 265 template <class BidiIterator, class Allocator, class traits>
 266 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
 267 {
 268    bool take_first, take_second;
 269    const re_alt* jmp = static_cast<const re_alt*>(pstate);
 270
 271    // find out which of these two alternatives we need to take:
 272    if(position == last)
 273    {
 274       take_first = jmp->can_be_null & mask_take;
 275       take_second = jmp->can_be_null & mask_skip;
 276    }
 277    else
 278    {
 279       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
 280       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
 281   }
 282
 283    if(take_first)
 284    {
 285       // we can take the first alternative,
 286       // see if we need to push next alternative:
 287       if(take_second)
 288       {
 289          BidiIterator oldposition(position);
 290          const re_syntax_base* old_pstate = jmp->alt.p;
 291          pstate = pstate->next.p;
 292          m_have_then = false;
 293          if(!match_all_states())
 294          {
 295             pstate = old_pstate;
 296             position = oldposition;
 297             if(m_have_then)
 298             {
 299                m_can_backtrack = true;
 300                m_have_then = false;
 301                return false;
 302             }
 303          }
 304          m_have_then = false;
 305          return m_can_backtrack;
 306       }
 307       pstate = pstate->next.p;
 308       return true;
 309    }
 310    if(take_second)
 311    {
 312       pstate = jmp->alt.p;
 313       return true;
 314    }
 315    return false;  // neither option is possible
 316 }
 317
 318 template <class BidiIterator, class Allocator, class traits>
 319 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
 320 {
 321 #ifdef BOOST_MSVC
 322 #pragma warning(push)
 323 #pragma warning(disable:4127 4244)
 324 #endif
 325    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 326    //
 327    // Always copy the repeat count, so that the state is restored
 328    // when we exit this scope:
 329    //
 330    repeater_count<BidiIterator> r(rep->state_id, &next_count, position, this->recursion_stack.size() ? this->recursion_stack.back().idx : INT_MIN + 3);
 331    //
 332    // If we've had at least one repeat already, and the last one
 333    // matched the NULL string then set the repeat count to
 334    // maximum:
 335    //
 336    next_count->check_null_repeat(position, rep->max);
 337
 338    // find out which of these two alternatives we need to take:
 339    bool take_first, take_second;
 340    if(position == last)
 341    {
 342       take_first = rep->can_be_null & mask_take;
 343       take_second = rep->can_be_null & mask_skip;
 344    }
 345    else
 346    {
 347       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
 348       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
 349    }
 350
 351    if(next_count->get_count() < rep->min)
 352    {
 353       // we must take the repeat:
 354       if(take_first)
 355       {
 356          // increase the counter:
 357          ++(*next_count);
 358          pstate = rep->next.p;
 359          return match_all_states();
 360       }
 361       return false;
 362    }
 363    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 364    if(greedy)
 365    {
 366       // try and take the repeat if we can:
 367       if((next_count->get_count() < rep->max) && take_first)
 368       {
 369          // store position in case we fail:
 370          BidiIterator pos = position;
 371          // increase the counter:
 372          ++(*next_count);
 373          pstate = rep->next.p;
 374          if(match_all_states())
 375             return true;
 376          if(!m_can_backtrack)
 377             return false;
 378          // failed repeat, reset posistion and fall through for alternative:
 379          position = pos;
 380       }
 381       if(take_second)
 382       {
 383          pstate = rep->alt.p;
 384          return true;
 385       }
 386       return false; // can't take anything, fail...
 387    }
 388    else // non-greedy
 389    {
 390       // try and skip the repeat if we can:
 391       if(take_second)
 392       {
 393          // store position in case we fail:
 394          BidiIterator pos = position;
 395          pstate = rep->alt.p;
 396          if(match_all_states())
 397             return true;
 398          if(!m_can_backtrack)
 399             return false;
 400          // failed alternative, reset posistion and fall through for repeat:
 401          position = pos;
 402       }
 403       if((next_count->get_count() < rep->max) && take_first)
 404       {
 405          // increase the counter:
 406          ++(*next_count);
 407          pstate = rep->next.p;
 408          return match_all_states();
 409       }
 410    }
 411    return false;
 412 #ifdef BOOST_MSVC
 413 #pragma warning(pop)
 414 #endif
 415 }
 416
 417 template <class BidiIterator, class Allocator, class traits>
 418 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 419 {
 420 #ifdef BOOST_MSVC
 421 #pragma warning(push)
 422 #pragma warning(disable:4127)
 423 #endif
 424    unsigned count = 0;
 425    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 426    re_syntax_base* psingle = rep->next.p;
 427    // match compulsary repeats first:
 428    while(count < rep->min)
 429    {
 430       pstate = psingle;
 431       if(!match_wild())
 432          return false;
 433       ++count;
 434    }
 435    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 436    if(greedy)
 437    {
 438       // normal repeat:
 439       while(count < rep->max)
 440       {
 441          pstate = psingle;
 442          if(!match_wild())
 443             break;
 444          ++count;
 445       }
 446       if((rep->leading) && (count < rep->max))
 447          restart = position;
 448       pstate = rep;
 449       return backtrack_till_match(count - rep->min);
 450    }
 451    else
 452    {
 453       // non-greedy, keep trying till we get a match:
 454       BidiIterator save_pos;
 455       do
 456       {
 457          if((rep->leading) && (rep->max == UINT_MAX))
 458             restart = position;
 459          pstate = rep->alt.p;
 460          save_pos = position;
 461          ++state_count;
 462          if(match_all_states())
 463             return true;
 464          if((count >= rep->max) || !m_can_backtrack)
 465             return false;
 466          ++count;
 467          pstate = psingle;
 468          position = save_pos;
 469          if(!match_wild())
 470             return false;
 471       }while(true);
 472    }
 473 #ifdef BOOST_MSVC
 474 #pragma warning(pop)
 475 #endif
 476 }
 477
 478 template <class BidiIterator, class Allocator, class traits>
 479 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 480 {
 481 #ifdef BOOST_MSVC
 482 #pragma warning(push)
 483 #pragma warning(disable:4127)
 484 #endif
 485    if(m_match_flags & match_not_dot_null)
 486       return match_dot_repeat_slow();
 487    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 488       return match_dot_repeat_slow();
 489    //
 490    // start by working out how much we can skip:
 491    //
 492    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 493 #ifdef BOOST_MSVC
 494 #pragma warning(push)
 495 #pragma warning(disable:4267)
 496 #endif
 497    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 498    std::size_t count = (std::min)(static_cast<std::size_t>(::boost::BOOST_REGEX_DETAIL_NS::distance(position, last)), static_cast<std::size_t>(greedy ? rep->max : rep->min));
 499    if(rep->min > count)
 500    {
 501       position = last;
 502       return false;  // not enough text left to match
 503    }
 504    std::advance(position, count);
 505 #ifdef BOOST_MSVC
 506 #pragma warning(pop)
 507 #endif
 508    if((rep->leading) && (count < rep->max) && greedy)
 509       restart = position;
 510    if(greedy)
 511       return backtrack_till_match(count - rep->min);
 512
 513    // non-greedy, keep trying till we get a match:
 514    BidiIterator save_pos;
 515    do
 516    {
 517       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 518       {
 519          ++position;
 520          ++count;
 521       }
 522       if((rep->leading) && (rep->max == UINT_MAX))
 523          restart = position;
 524       pstate = rep->alt.p;
 525       save_pos = position;
 526       ++state_count;
 527       if(match_all_states())
 528          return true;
 529       if((count >= rep->max) || !m_can_backtrack)
 530          return false;
 531       if(save_pos == last)
 532          return false;
 533       position = ++save_pos;
 534       ++count;
 535    }while(true);
 536 #ifdef BOOST_MSVC
 537 #pragma warning(pop)
 538 #endif
 539 }
 540
 541 template <class BidiIterator, class Allocator, class traits>
 542 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 543 {
 544 #ifdef BOOST_MSVC
 545 #pragma warning(push)
 546 #pragma warning(disable:4127)
 547 #pragma warning(disable:4267)
 548 #endif
 549 #ifdef __BORLANDC__
 550 #pragma option push -w-8008 -w-8066 -w-8004
 551 #endif
 552    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 553    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 554    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 555    //
 556    // start by working out how much we can skip:
 557    //
 558    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 559    std::size_t count, desired;
 560    if(::boost::is_random_access_iterator<BidiIterator>::value)
 561    {
 562       desired =
 563          (std::min)(
 564             (std::size_t)(greedy ? rep->max : rep->min),
 565             (std::size_t)::boost::BOOST_REGEX_DETAIL_NS::distance(position, last));
 566       count = desired;
 567       ++desired;
 568       if(icase)
 569       {
 570          while(--desired && (traits_inst.translate_nocase(*position) == what))
 571          {
 572             ++position;
 573          }
 574       }
 575       else
 576       {
 577          while(--desired && (traits_inst.translate(*position) == what))
 578          {
 579             ++position;
 580          }
 581       }
 582       count = count - desired;
 583    }
 584    else
 585    {
 586       count = 0;
 587       desired = greedy ? rep->max : rep->min;
 588       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 589       {
 590          ++position;
 591          ++count;
 592       }
 593    }
 594    if((rep->leading) && (count < rep->max) && greedy)
 595       restart = position;
 596    if(count < rep->min)
 597       return false;
 598
 599    if(greedy)
 600       return backtrack_till_match(count - rep->min);
 601
 602    // non-greedy, keep trying till we get a match:
 603    BidiIterator save_pos;
 604    do
 605    {
 606       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 607       {
 608          if((traits_inst.translate(*position, icase) == what))
 609          {
 610             ++position;
 611             ++count;
 612          }
 613          else
 614             return false;  // counldn't repeat even though it was the only option
 615       }
 616       if((rep->leading) && (rep->max == UINT_MAX))
 617          restart = position;
 618       pstate = rep->alt.p;
 619       save_pos = position;
 620       ++state_count;
 621       if(match_all_states())
 622          return true;
 623       if((count >= rep->max) || !m_can_backtrack)
 624          return false;
 625       position = save_pos;
 626       if(position == last)
 627          return false;
 628       if(traits_inst.translate(*position, icase) == what)
 629       {
 630          ++position;
 631          ++count;
 632       }
 633       else
 634       {
 635          return false;
 636       }
 637    }while(true);
 638 #ifdef __BORLANDC__
 639 #pragma option pop
 640 #endif
 641 #ifdef BOOST_MSVC
 642 #pragma warning(pop)
 643 #endif
 644 }
 645
 646 template <class BidiIterator, class Allocator, class traits>
 647 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 648 {
 649 #ifdef BOOST_MSVC
 650 #pragma warning(push)
 651 #pragma warning(disable:4127)
 652 #endif
 653 #ifdef __BORLANDC__
 654 #pragma option push -w-8008 -w-8066 -w-8004
 655 #endif
 656    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 657    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 658    unsigned count = 0;
 659    //
 660    // start by working out how much we can skip:
 661    //
 662    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 663    std::size_t desired = greedy ? rep->max : rep->min;
 664    if(::boost::is_random_access_iterator<BidiIterator>::value)
 665    {
 666       BidiIterator end = position;
 667       // Move end forward by "desired", preferably without using distance or advance if we can
 668       // as these can be slow for some iterator types.
 669       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
 670       if(desired >= len)
 671          end = last;
 672       else
 673          std::advance(end, desired);
 674       BidiIterator origin(position);
 675       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 676       {
 677          ++position;
 678       }
 679       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
 680    }
 681    else
 682    {
 683       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 684       {
 685          ++position;
 686          ++count;
 687       }
 688    }
 689    if((rep->leading) && (count < rep->max) && greedy)
 690       restart = position;
 691    if(count < rep->min)
 692       return false;
 693
 694    if(greedy)
 695       return backtrack_till_match(count - rep->min);
 696
 697    // non-greedy, keep trying till we get a match:
 698    BidiIterator save_pos;
 699    do
 700    {
 701       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 702       {
 703          if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 704          {
 705             ++position;
 706             ++count;
 707          }
 708          else
 709             return false;  // counldn't repeat even though it was the only option
 710       }
 711       if((rep->leading) && (rep->max == UINT_MAX))
 712          restart = position;
 713       pstate = rep->alt.p;
 714       save_pos = position;
 715       ++state_count;
 716       if(match_all_states())
 717          return true;
 718       if((count >= rep->max) || !m_can_backtrack)
 719          return false;
 720       position = save_pos;
 721       if(position == last)
 722          return false;
 723       if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 724       {
 725          ++position;
 726          ++count;
 727       }
 728       else
 729       {
 730          return false;
 731       }
 732    }while(true);
 733 #ifdef __BORLANDC__
 734 #pragma option pop
 735 #endif
 736 #ifdef BOOST_MSVC
 737 #pragma warning(pop)
 738 #endif
 739 }
 740
 741 template <class BidiIterator, class Allocator, class traits>
 742 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 743 {
 744 #ifdef BOOST_MSVC
 745 #pragma warning(push)
 746 #pragma warning(disable:4127)
 747 #endif
 748 #ifdef __BORLANDC__
 749 #pragma option push -w-8008 -w-8066 -w-8004
 750 #endif
 751    typedef typename traits::char_class_type char_class_type;
 752    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 753    const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
 754    unsigned count = 0;
 755    //
 756    // start by working out how much we can skip:
 757    //
 758    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 759    std::size_t desired = greedy ? rep->max : rep->min;
 760    if(::boost::is_random_access_iterator<BidiIterator>::value)
 761    {
 762       BidiIterator end = position;
 763       // Move end forward by "desired", preferably without using distance or advance if we can
 764       // as these can be slow for some iterator types.
 765       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::BOOST_REGEX_DETAIL_NS::distance(position, last);
 766       if(desired >= len)
 767          end = last;
 768       else
 769          std::advance(end, desired);
 770       BidiIterator origin(position);
 771       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 772       {
 773          ++position;
 774       }
 775       count = (unsigned)::boost::BOOST_REGEX_DETAIL_NS::distance(origin, position);
 776    }
 777    else
 778    {
 779       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 780       {
 781          ++position;
 782          ++count;
 783       }
 784    }
 785    if((rep->leading) && (count < rep->max) && greedy)
 786       restart = position;
 787    if(count < rep->min)
 788       return false;
 789
 790    if(greedy)
 791       return backtrack_till_match(count - rep->min);
 792
 793    // non-greedy, keep trying till we get a match:
 794    BidiIterator save_pos;
 795    do
 796    {
 797       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 798       {
 799          if(position != re_is_set_member(position, last, set, re.get_data(), icase))
 800          {
 801             ++position;
 802             ++count;
 803          }
 804          else
 805             return false;  // counldn't repeat even though it was the only option
 806       }
 807       if((rep->leading) && (rep->max == UINT_MAX))
 808          restart = position;
 809       pstate = rep->alt.p;
 810       save_pos = position;
 811       ++state_count;
 812       if(match_all_states())
 813          return true;
 814       if((count >= rep->max) || !m_can_backtrack)
 815          return false;
 816       position = save_pos;
 817       if(position == last)
 818          return false;
 819       if(position != re_is_set_member(position, last, set, re.get_data(), icase))
 820       {
 821          ++position;
 822          ++count;
 823       }
 824       else
 825       {
 826          return false;
 827       }
 828    }while(true);
 829 #ifdef __BORLANDC__
 830 #pragma option pop
 831 #endif
 832 #ifdef BOOST_MSVC
 833 #pragma warning(pop)
 834 #endif
 835 }
 836
 837 template <class BidiIterator, class Allocator, class traits>
 838 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
 839 {
 840 #ifdef BOOST_MSVC
 841 #pragma warning(push)
 842 #pragma warning(disable:4127)
 843 #endif
 844    if(!m_can_backtrack)
 845       return false;
 846    if((m_match_flags & match_partial) && (position == last))
 847       m_has_partial_match = true;
 848
 849    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 850    BidiIterator backtrack = position;
 851    if(position == last)
 852    {
 853       if(rep->can_be_null & mask_skip)
 854       {
 855          pstate = rep->alt.p;
 856          if(match_all_states())
 857             return true;
 858       }
 859       if(count)
 860       {
 861          position = --backtrack;
 862          --count;
 863       }
 864       else
 865          return false;
 866    }
 867    do
 868    {
 869       while(count && !can_start(*position, rep->_map, mask_skip))
 870       {
 871          --position;
 872          --count;
 873          ++state_count;
 874       }
 875       pstate = rep->alt.p;
 876       backtrack = position;
 877       if(match_all_states())
 878          return true;
 879       if(count == 0)
 880          return false;
 881       position = --backtrack;
 882       ++state_count;
 883       --count;
 884    }while(true);
 885 #ifdef BOOST_MSVC
 886 #pragma warning(pop)
 887 #endif
 888 }
 889
 890 template <class BidiIterator, class Allocator, class traits>
 891 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
 892 {
 893    BOOST_ASSERT(pstate->type == syntax_element_recurse);
 894    //
 895    // Set new call stack:
 896    //
 897    if(recursion_stack.capacity() == 0)
 898    {
 899       recursion_stack.reserve(50);
 900    }
 901    recursion_stack.push_back(recursion_info<results_type>());
 902    recursion_stack.back().preturn_address = pstate->next.p;
 903    recursion_stack.back().results = *m_presult;
 904    recursion_stack.back().repeater_stack = next_count;
 905    pstate = static_cast<const re_jump*>(pstate)->alt.p;
 906    recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
 907
 908    repeater_count<BidiIterator>* saved = next_count;
 909    repeater_count<BidiIterator> r(&next_count); // resets all repeat counts since we're recursing and starting fresh on those
 910    next_count = &r;
 911    bool can_backtrack = m_can_backtrack;
 912    bool result = match_all_states();
 913    m_can_backtrack = can_backtrack;
 914    next_count = saved;
 915
 916    if(!result)
 917    {
 918       next_count = recursion_stack.back().repeater_stack;
 919       *m_presult = recursion_stack.back().results;
 920       recursion_stack.pop_back();
 921       return false;
 922    }
 923    return true;
 924 }
 925
 926 template <class BidiIterator, class Allocator, class traits>
 927 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
 928 {
 929    int index = static_cast<const re_brace*>(pstate)->index;
 930    icase = static_cast<const re_brace*>(pstate)->icase;
 931    if(index > 0)
 932    {
 933       if((m_match_flags & match_nosubs) == 0)
 934       {
 935          m_presult->set_second(position, index);
 936       }
 937       if(!recursion_stack.empty())
 938       {
 939          if(index == recursion_stack.back().idx)
 940          {
 941             recursion_info<results_type> saved = recursion_stack.back();
 942             recursion_stack.pop_back();
 943             pstate = saved.preturn_address;
 944             repeater_count<BidiIterator>* saved_count = next_count;
 945             next_count = saved.repeater_stack;
 946             *m_presult = saved.results;
 947             if(!match_all_states())
 948             {
 949                recursion_stack.push_back(saved);
 950                next_count = saved_count;
 951                return false;
 952             }
 953          }
 954       }
 955    }
 956    else if((index < 0) && (index != -4))
 957    {
 958       // matched forward lookahead:
 959       pstate = 0;
 960       return true;
 961    }
 962    pstate = pstate ? pstate->next.p : 0;
 963    return true;
 964 }
 965
 966 template <class BidiIterator, class Allocator, class traits>
 967 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
 968 {
 969    if(!recursion_stack.empty())
 970    {
 971       BOOST_ASSERT(0 == recursion_stack.back().idx);
 972       const re_syntax_base* saved_state = pstate = recursion_stack.back().preturn_address;
 973       *m_presult = recursion_stack.back().results;
 974       recursion_stack.pop_back();
 975       if(!match_all_states())
 976       {
 977          recursion_stack.push_back(recursion_info<results_type>());
 978          recursion_stack.back().preturn_address = saved_state;
 979          recursion_stack.back().results = *m_presult;
 980          return false;
 981       }
 982       return true;
 983    }
 984    if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
 985       return false;
 986    if((m_match_flags & match_all) && (position != last))
 987       return false;
 988    if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
 989       return false;
 990    m_presult->set_second(position);
 991    pstate = 0;
 992    m_has_found_match = true;
 993    if((m_match_flags & match_posix) == match_posix)
 994    {
 995       m_result.maybe_assign(*m_presult);
 996       if((m_match_flags & match_any) == 0)
 997          return false;
 998    }
 999 #ifdef BOOST_REGEX_MATCH_EXTRA
1000    if(match_extra & m_match_flags)
1001    {
1002       for(unsigned i = 0; i < m_presult->size(); ++i)
1003          if((*m_presult)[i].matched)
1004             ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
1005    }
1006 #endif
1007    return true;
1008 }
1009
1010 template <class BidiIterator, class Allocator, class traits>
1011 bool perl_matcher<BidiIterator, Allocator, traits>::match_commit()
1012 {
1013    m_can_backtrack = false;
1014    int action = static_cast<const re_commit*>(pstate)->action;
1015    switch(action)
1016    {
1017    case commit_commit:
1018       restart = last;
1019       break;
1020    case commit_skip:
1021       restart = position;
1022       break;
1023    }
1024    pstate = pstate->next.p;
1025    return true;
1026 }
1027
1028 template <class BidiIterator, class Allocator, class traits>
1029 bool perl_matcher<BidiIterator, Allocator, traits>::match_then()
1030 {
1031    pstate = pstate->next.p;
1032    if(match_all_states())
1033       return true;
1034    m_can_backtrack = false;
1035    m_have_then = true;
1036    return false;
1037 }
1038
1039 template <class BidiIterator, class Allocator, class traits>
1040 bool perl_matcher<BidiIterator, Allocator, traits>::skip_until_paren(int index, bool have_match)
1041 {
1042    while(pstate)
1043    {
1044       if(pstate->type == syntax_element_endmark)
1045       {
1046          if(static_cast<const re_brace*>(pstate)->index == index)
1047          {
1048             if(have_match)
1049                return this->match_endmark();
1050             pstate = pstate->next.p;
1051             return true;
1052          }
1053          else
1054          {
1055             // Unenclosed closing ), occurs when (*ACCEPT) is inside some other
1056             // parenthesis which may or may not have other side effects associated with it.
1057             bool r = match_endmark();
1058             m_have_accept = true;
1059             if(!pstate)
1060                return r;
1061          }
1062          continue;
1063       }
1064       else if(pstate->type == syntax_element_match)
1065          return true;
1066       else if(pstate->type == syntax_element_startmark)
1067       {
1068          int idx = static_cast<const re_brace*>(pstate)->index;
1069          pstate = pstate->next.p;
1070          skip_until_paren(idx, false);
1071          continue;
1072       }
1073       pstate = pstate->next.p;
1074    }
1075    return true;
1076 }
1077
1078
1079 } // namespace BOOST_REGEX_DETAIL_NS
1080 } // namespace boost
1081 #ifdef BOOST_MSVC
1082 #pragma warning(pop)
1083 #endif
1084
1085 #ifdef BOOST_MSVC
1086 #pragma warning(push)
1087 #pragma warning(disable: 4103)
1088 #endif
1089 #ifdef BOOST_HAS_ABI_HEADERS
1090 #  include BOOST_ABI_SUFFIX
1091 #endif
1092 #ifdef BOOST_MSVC
1093 #pragma warning(pop)
1094 #endif
1095
1096 #endif
1097