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 re_detail{
  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[29] =
  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    };
  99
 100    if(state_count > max_state_count)
 101       raise_error(traits_inst, regex_constants::error_space);
 102    while(pstate)
 103    {
 104       matcher_proc_type proc = s_match_vtable[pstate->type];
 105       ++state_count;
 106       if(!(this->*proc)())
 107       {
 108          if((m_match_flags & match_partial) && (position == last) && (position != search_base))
 109             m_has_partial_match = true;
 110          return 0;
 111       }
 112    }
 113    return true;
 114 }
 115
 116 template <class BidiIterator, class Allocator, class traits>
 117 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
 118 {
 119    int index = static_cast<const re_brace*>(pstate)->index;
 120    bool r = true;
 121    switch(index)
 122    {
 123    case 0:
 124       pstate = pstate->next.p;
 125       break;
 126    case -1:
 127    case -2:
 128       {
 129          // forward lookahead assert:
 130          BidiIterator old_position(position);
 131          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 132          pstate = pstate->next.p->next.p;
 133          r = match_all_states();
 134          pstate = next_pstate;
 135          position = old_position;
 136          if((r && (index != -1)) || (!r && (index != -2)))
 137             r = false;
 138          else
 139             r = true;
 140          break;
 141       }
 142    case -3:
 143       {
 144          // independent sub-expression:
 145          bool old_independent = m_independent;
 146          m_independent = true;
 147          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 148          pstate = pstate->next.p->next.p;
 149          r = match_all_states();
 150          pstate = next_pstate;
 151          m_independent = old_independent;
 152 #ifdef BOOST_REGEX_MATCH_EXTRA
 153          if(r && (m_match_flags & match_extra))
 154          {
 155             //
 156             // our captures have been stored in *m_presult
 157             // we need to unpack them, and insert them
 158             // back in the right order when we unwind the stack:
 159             //
 160             unsigned i;
 161             match_results<BidiIterator, Allocator> tm(*m_presult);
 162             for(i = 0; i < tm.size(); ++i)
 163                (*m_presult)[i].get_captures().clear();
 164             // match everything else:
 165             r = match_all_states();
 166             // now place the stored captures back:
 167             for(i = 0; i < tm.size(); ++i)
 168             {
 169                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
 170                seq& s1 = (*m_presult)[i].get_captures();
 171                const seq& s2 = tm[i].captures();
 172                s1.insert(
 173                   s1.end(),
 174                   s2.begin(),
 175                   s2.end());
 176             }
 177          }
 178 #endif
 179          break;
 180       }
 181    case -4:
 182       {
 183       // conditional expression:
 184       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
 185       BOOST_ASSERT(alt->type == syntax_element_alt);
 186       pstate = alt->next.p;
 187       if(pstate->type == syntax_element_assert_backref)
 188       {
 189          if(!match_assert_backref())
 190             pstate = alt->alt.p;
 191          break;
 192       }
 193       else
 194       {
 195          // zero width assertion, have to match this recursively:
 196          BOOST_ASSERT(pstate->type == syntax_element_startmark);
 197          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
 198          BidiIterator saved_position = position;
 199          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
 200          pstate = pstate->next.p->next.p;
 201          bool r = match_all_states();
 202          position = saved_position;
 203          if(negated)
 204             r = !r;
 205          if(r)
 206             pstate = next_pstate;
 207          else
 208             pstate = alt->alt.p;
 209          break;
 210       }
 211       }
 212    case -5:
 213       {
 214          // Reset start of $0, since we have a \K escape
 215          backup_subex<BidiIterator> sub(*m_presult, 0);
 216          m_presult->set_first(position, 0, true);
 217          pstate = pstate->next.p;
 218          r = match_all_states();
 219          if(r == false)
 220             sub.restore(*m_presult);
 221          break;
 222       }
 223    default:
 224    {
 225       BOOST_ASSERT(index > 0);
 226       if((m_match_flags & match_nosubs) == 0)
 227       {
 228          backup_subex<BidiIterator> sub(*m_presult, index);
 229          m_presult->set_first(position, index);
 230          pstate = pstate->next.p;
 231          r = match_all_states();
 232          if(r == false)
 233             sub.restore(*m_presult);
 234 #ifdef BOOST_REGEX_MATCH_EXTRA
 235          //
 236          // we have a match, push the capture information onto the stack:
 237          //
 238          else if(sub.get().matched && (match_extra & m_match_flags))
 239             ((*m_presult)[index]).get_captures().push_back(sub.get());
 240 #endif
 241       }
 242       else
 243       {
 244          pstate = pstate->next.p;
 245       }
 246       break;
 247    }
 248    }
 249    return r;
 250 }
 251
 252 template <class BidiIterator, class Allocator, class traits>
 253 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
 254 {
 255    bool take_first, take_second;
 256    const re_alt* jmp = static_cast<const re_alt*>(pstate);
 257
 258    // find out which of these two alternatives we need to take:
 259    if(position == last)
 260    {
 261       take_first = jmp->can_be_null & mask_take;
 262       take_second = jmp->can_be_null & mask_skip;
 263    }
 264    else
 265    {
 266       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
 267       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
 268   }
 269
 270    if(take_first)
 271    {
 272       // we can take the first alternative,
 273       // see if we need to push next alternative:
 274       if(take_second)
 275       {
 276          BidiIterator oldposition(position);
 277          const re_syntax_base* old_pstate = jmp->alt.p;
 278          pstate = pstate->next.p;
 279          if(!match_all_states())
 280          {
 281             pstate = old_pstate;
 282             position = oldposition;
 283          }
 284          return true;
 285       }
 286       pstate = pstate->next.p;
 287       return true;
 288    }
 289    if(take_second)
 290    {
 291       pstate = jmp->alt.p;
 292       return true;
 293    }
 294    return false;  // neither option is possible
 295 }
 296
 297 template <class BidiIterator, class Allocator, class traits>
 298 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
 299 {
 300 #ifdef BOOST_MSVC
 301 #pragma warning(push)
 302 #pragma warning(disable:4127 4244)
 303 #endif
 304    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 305    //
 306    // Always copy the repeat count, so that the state is restored
 307    // when we exit this scope:
 308    //
 309    repeater_count<BidiIterator> r(rep->state_id, &next_count, position);
 310    //
 311    // If we've had at least one repeat already, and the last one
 312    // matched the NULL string then set the repeat count to
 313    // maximum:
 314    //
 315    next_count->check_null_repeat(position, rep->max);
 316
 317    // find out which of these two alternatives we need to take:
 318    bool take_first, take_second;
 319    if(position == last)
 320    {
 321       take_first = rep->can_be_null & mask_take;
 322       take_second = rep->can_be_null & mask_skip;
 323    }
 324    else
 325    {
 326       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
 327       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
 328    }
 329
 330    if(next_count->get_count() < rep->min)
 331    {
 332       // we must take the repeat:
 333       if(take_first)
 334       {
 335          // increase the counter:
 336          ++(*next_count);
 337          pstate = rep->next.p;
 338          return match_all_states();
 339       }
 340       return false;
 341    }
 342    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 343    if(greedy)
 344    {
 345       // try and take the repeat if we can:
 346       if((next_count->get_count() < rep->max) && take_first)
 347       {
 348          // store position in case we fail:
 349          BidiIterator pos = position;
 350          // increase the counter:
 351          ++(*next_count);
 352          pstate = rep->next.p;
 353          if(match_all_states())
 354             return true;
 355          // failed repeat, reset posistion and fall through for alternative:
 356          position = pos;
 357       }
 358       if(take_second)
 359       {
 360          pstate = rep->alt.p;
 361          return true;
 362       }
 363       return false; // can't take anything, fail...
 364    }
 365    else // non-greedy
 366    {
 367       // try and skip the repeat if we can:
 368       if(take_second)
 369       {
 370          // store position in case we fail:
 371          BidiIterator pos = position;
 372          pstate = rep->alt.p;
 373          if(match_all_states())
 374             return true;
 375          // failed alternative, reset posistion and fall through for repeat:
 376          position = pos;
 377       }
 378       if((next_count->get_count() < rep->max) && take_first)
 379       {
 380          // increase the counter:
 381          ++(*next_count);
 382          pstate = rep->next.p;
 383          return match_all_states();
 384       }
 385    }
 386    return false;
 387 #ifdef BOOST_MSVC
 388 #pragma warning(pop)
 389 #endif
 390 }
 391
 392 template <class BidiIterator, class Allocator, class traits>
 393 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 394 {
 395 #ifdef BOOST_MSVC
 396 #pragma warning(push)
 397 #pragma warning(disable:4127)
 398 #endif
 399    unsigned count = 0;
 400    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 401    re_syntax_base* psingle = rep->next.p;
 402    // match compulsary repeats first:
 403    while(count < rep->min)
 404    {
 405       pstate = psingle;
 406       if(!match_wild())
 407          return false;
 408       ++count;
 409    }
 410    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 411    if(greedy)
 412    {
 413       // normal repeat:
 414       while(count < rep->max)
 415       {
 416          pstate = psingle;
 417          if(!match_wild())
 418             break;
 419          ++count;
 420       }
 421       if((rep->leading) && (count < rep->max))
 422          restart = position;
 423       pstate = rep;
 424       return backtrack_till_match(count - rep->min);
 425    }
 426    else
 427    {
 428       // non-greedy, keep trying till we get a match:
 429       BidiIterator save_pos;
 430       do
 431       {
 432          if((rep->leading) && (rep->max == UINT_MAX))
 433             restart = position;
 434          pstate = rep->alt.p;
 435          save_pos = position;
 436          ++state_count;
 437          if(match_all_states())
 438             return true;
 439          if(count >= rep->max)
 440             return false;
 441          ++count;
 442          pstate = psingle;
 443          position = save_pos;
 444          if(!match_wild())
 445             return false;
 446       }while(true);
 447    }
 448 #ifdef BOOST_MSVC
 449 #pragma warning(pop)
 450 #endif
 451 }
 452
 453 template <class BidiIterator, class Allocator, class traits>
 454 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 455 {
 456 #ifdef BOOST_MSVC
 457 #pragma warning(push)
 458 #pragma warning(disable:4127)
 459 #endif
 460    if(m_match_flags & match_not_dot_null)
 461       return match_dot_repeat_slow();
 462    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 463       return match_dot_repeat_slow();
 464    //
 465    // start by working out how much we can skip:
 466    //
 467    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 468 #ifdef BOOST_MSVC
 469 #pragma warning(push)
 470 #pragma warning(disable:4267)
 471 #endif
 472    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 473    std::size_t count = (std::min)(static_cast<std::size_t>(::boost::re_detail::distance(position, last)), static_cast<std::size_t>(greedy ? rep->max : rep->min));
 474    if(rep->min > count)
 475    {
 476       position = last;
 477       return false;  // not enough text left to match
 478    }
 479    std::advance(position, count);
 480 #ifdef BOOST_MSVC
 481 #pragma warning(pop)
 482 #endif
 483    if((rep->leading) && (count < rep->max) && greedy)
 484       restart = position;
 485    if(greedy)
 486       return backtrack_till_match(count - rep->min);
 487
 488    // non-greedy, keep trying till we get a match:
 489    BidiIterator save_pos;
 490    do
 491    {
 492       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 493       {
 494          ++position;
 495          ++count;
 496       }
 497       if((rep->leading) && (rep->max == UINT_MAX))
 498          restart = position;
 499       pstate = rep->alt.p;
 500       save_pos = position;
 501       ++state_count;
 502       if(match_all_states())
 503          return true;
 504       if(count >= rep->max)
 505          return false;
 506       if(save_pos == last)
 507          return false;
 508       position = ++save_pos;
 509       ++count;
 510    }while(true);
 511 #ifdef BOOST_MSVC
 512 #pragma warning(pop)
 513 #endif
 514 }
 515
 516 template <class BidiIterator, class Allocator, class traits>
 517 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 518 {
 519 #ifdef BOOST_MSVC
 520 #pragma warning(push)
 521 #pragma warning(disable:4127)
 522 #pragma warning(disable:4267)
 523 #endif
 524 #ifdef __BORLANDC__
 525 #pragma option push -w-8008 -w-8066 -w-8004
 526 #endif
 527    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 528    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 529    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 530    //
 531    // start by working out how much we can skip:
 532    //
 533    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 534    std::size_t count, desired;
 535    if(::boost::is_random_access_iterator<BidiIterator>::value)
 536    {
 537       desired =
 538          (std::min)(
 539             (std::size_t)(greedy ? rep->max : rep->min),
 540             (std::size_t)::boost::re_detail::distance(position, last));
 541       count = desired;
 542       ++desired;
 543       if(icase)
 544       {
 545          while(--desired && (traits_inst.translate_nocase(*position) == what))
 546          {
 547             ++position;
 548          }
 549       }
 550       else
 551       {
 552          while(--desired && (traits_inst.translate(*position) == what))
 553          {
 554             ++position;
 555          }
 556       }
 557       count = count - desired;
 558    }
 559    else
 560    {
 561       count = 0;
 562       desired = greedy ? rep->max : rep->min;
 563       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 564       {
 565          ++position;
 566          ++count;
 567       }
 568    }
 569    if((rep->leading) && (count < rep->max) && greedy)
 570       restart = position;
 571    if(count < rep->min)
 572       return false;
 573
 574    if(greedy)
 575       return backtrack_till_match(count - rep->min);
 576
 577    // non-greedy, keep trying till we get a match:
 578    BidiIterator save_pos;
 579    do
 580    {
 581       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 582       {
 583          if((traits_inst.translate(*position, icase) == what))
 584          {
 585             ++position;
 586             ++count;
 587          }
 588          else
 589             return false;  // counldn't repeat even though it was the only option
 590       }
 591       if((rep->leading) && (rep->max == UINT_MAX))
 592          restart = position;
 593       pstate = rep->alt.p;
 594       save_pos = position;
 595       ++state_count;
 596       if(match_all_states())
 597          return true;
 598       if(count >= rep->max)
 599          return false;
 600       position = save_pos;
 601       if(position == last)
 602          return false;
 603       if(traits_inst.translate(*position, icase) == what)
 604       {
 605          ++position;
 606          ++count;
 607       }
 608       else
 609       {
 610          return false;
 611       }
 612    }while(true);
 613 #ifdef __BORLANDC__
 614 #pragma option pop
 615 #endif
 616 #ifdef BOOST_MSVC
 617 #pragma warning(pop)
 618 #endif
 619 }
 620
 621 template <class BidiIterator, class Allocator, class traits>
 622 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 623 {
 624 #ifdef BOOST_MSVC
 625 #pragma warning(push)
 626 #pragma warning(disable:4127)
 627 #endif
 628 #ifdef __BORLANDC__
 629 #pragma option push -w-8008 -w-8066 -w-8004
 630 #endif
 631    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 632    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 633    unsigned count = 0;
 634    //
 635    // start by working out how much we can skip:
 636    //
 637    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 638    std::size_t desired = greedy ? rep->max : rep->min;
 639    if(::boost::is_random_access_iterator<BidiIterator>::value)
 640    {
 641       BidiIterator end = position;
 642       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 643       BidiIterator origin(position);
 644       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 645       {
 646          ++position;
 647       }
 648       count = (unsigned)::boost::re_detail::distance(origin, position);
 649    }
 650    else
 651    {
 652       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 653       {
 654          ++position;
 655          ++count;
 656       }
 657    }
 658    if((rep->leading) && (count < rep->max) && greedy)
 659       restart = position;
 660    if(count < rep->min)
 661       return false;
 662
 663    if(greedy)
 664       return backtrack_till_match(count - rep->min);
 665
 666    // non-greedy, keep trying till we get a match:
 667    BidiIterator save_pos;
 668    do
 669    {
 670       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 671       {
 672          if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 673          {
 674             ++position;
 675             ++count;
 676          }
 677          else
 678             return false;  // counldn't repeat even though it was the only option
 679       }
 680       if((rep->leading) && (rep->max == UINT_MAX))
 681          restart = position;
 682       pstate = rep->alt.p;
 683       save_pos = position;
 684       ++state_count;
 685       if(match_all_states())
 686          return true;
 687       if(count >= rep->max)
 688          return false;
 689       position = save_pos;
 690       if(position == last)
 691          return false;
 692       if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 693       {
 694          ++position;
 695          ++count;
 696       }
 697       else
 698       {
 699          return false;
 700       }
 701    }while(true);
 702 #ifdef __BORLANDC__
 703 #pragma option pop
 704 #endif
 705 #ifdef BOOST_MSVC
 706 #pragma warning(pop)
 707 #endif
 708 }
 709
 710 template <class BidiIterator, class Allocator, class traits>
 711 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 712 {
 713 #ifdef BOOST_MSVC
 714 #pragma warning(push)
 715 #pragma warning(disable:4127)
 716 #endif
 717 #ifdef __BORLANDC__
 718 #pragma option push -w-8008 -w-8066 -w-8004
 719 #endif
 720    typedef typename traits::char_class_type char_class_type;
 721    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 722    const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
 723    unsigned count = 0;
 724    //
 725    // start by working out how much we can skip:
 726    //
 727    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 728    std::size_t desired = greedy ? rep->max : rep->min;
 729    if(::boost::is_random_access_iterator<BidiIterator>::value)
 730    {
 731       BidiIterator end = position;
 732       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 733       BidiIterator origin(position);
 734       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 735       {
 736          ++position;
 737       }
 738       count = (unsigned)::boost::re_detail::distance(origin, position);
 739    }
 740    else
 741    {
 742       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 743       {
 744          ++position;
 745          ++count;
 746       }
 747    }
 748    if((rep->leading) && (count < rep->max) && greedy)
 749       restart = position;
 750    if(count < rep->min)
 751       return false;
 752
 753    if(greedy)
 754       return backtrack_till_match(count - rep->min);
 755
 756    // non-greedy, keep trying till we get a match:
 757    BidiIterator save_pos;
 758    do
 759    {
 760       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 761       {
 762          if(position != re_is_set_member(position, last, set, re.get_data(), icase))
 763          {
 764             ++position;
 765             ++count;
 766          }
 767          else
 768             return false;  // counldn't repeat even though it was the only option
 769       }
 770       if((rep->leading) && (rep->max == UINT_MAX))
 771          restart = position;
 772       pstate = rep->alt.p;
 773       save_pos = position;
 774       ++state_count;
 775       if(match_all_states())
 776          return true;
 777       if(count >= rep->max)
 778          return false;
 779       position = save_pos;
 780       if(position == last)
 781          return false;
 782       if(position != re_is_set_member(position, last, set, re.get_data(), icase))
 783       {
 784          ++position;
 785          ++count;
 786       }
 787       else
 788       {
 789          return false;
 790       }
 791    }while(true);
 792 #ifdef __BORLANDC__
 793 #pragma option pop
 794 #endif
 795 #ifdef BOOST_MSVC
 796 #pragma warning(pop)
 797 #endif
 798 }
 799
 800 template <class BidiIterator, class Allocator, class traits>
 801 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
 802 {
 803 #ifdef BOOST_MSVC
 804 #pragma warning(push)
 805 #pragma warning(disable:4127)
 806 #endif
 807    if((m_match_flags & match_partial) && (position == last))
 808       m_has_partial_match = true;
 809
 810    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 811    BidiIterator backtrack = position;
 812    if(position == last)
 813    {
 814       if(rep->can_be_null & mask_skip)
 815       {
 816          pstate = rep->alt.p;
 817          if(match_all_states())
 818             return true;
 819       }
 820       if(count)
 821       {
 822          position = --backtrack;
 823          --count;
 824       }
 825       else
 826          return false;
 827    }
 828    do
 829    {
 830       while(count && !can_start(*position, rep->_map, mask_skip))
 831       {
 832          --position;
 833          --count;
 834          ++state_count;
 835       }
 836       pstate = rep->alt.p;
 837       backtrack = position;
 838       if(match_all_states())
 839          return true;
 840       if(count == 0)
 841          return false;
 842       position = --backtrack;
 843       ++state_count;
 844       --count;
 845    }while(true);
 846 #ifdef BOOST_MSVC
 847 #pragma warning(pop)
 848 #endif
 849 }
 850
 851 } // namespace re_detail
 852 } // namespace boost
 853 #ifdef BOOST_MSVC
 854 #pragma warning(pop)
 855 #endif
 856
 857 #ifdef BOOST_MSVC
 858 #pragma warning(push)
 859 #pragma warning(disable: 4103)
 860 #endif
 861 #ifdef BOOST_HAS_ABI_HEADERS
 862 #  include BOOST_ABI_SUFFIX
 863 #endif
 864 #ifdef BOOST_MSVC
 865 #pragma warning(pop)
 866 #endif
 867
 868 #endif
 869