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