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    if(next_count->get_id() != rep->id)
 279    {
 280       // we're moving to a different repeat from the last
 281       // one, so set up a counter object and recurse:
 282       repeater_count<BidiIterator> r(rep->id, &next_count, position);
 283       return match_rep();
 284    }
 285    //
 286    // If we've had at least one repeat already, and the last one
 287    // matched the NULL string then set the repeat count to
 288    // maximum:
 289    //
 290    next_count->check_null_repeat(position, rep->max);
 291
 292    // find out which of these two alternatives we need to take:
 293    bool take_first, take_second;
 294    if(position == last)
 295    {
 296       take_first = rep->can_be_null & mask_take;
 297       take_second = rep->can_be_null & mask_skip;
 298    }
 299    else
 300    {
 301       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
 302       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
 303    }
 304
 305    if(next_count->get_count() < rep->min)
 306    {
 307       // we must take the repeat:
 308       if(take_first)
 309       {
 310          // increase the counter:
 311          ++(*next_count);
 312          pstate = rep->next.p;
 313          return match_all_states();
 314       }
 315       return false;
 316    }
 317    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 318    if(greedy)
 319    {
 320       // try and take the repeat if we can:
 321       if((next_count->get_count() < rep->max) && take_first)
 322       {
 323          // store position in case we fail:
 324          BidiIterator pos = position;
 325          // increase the counter:
 326          ++(*next_count);
 327          pstate = rep->next.p;
 328          if(match_all_states())
 329             return true;
 330          // failed repeat, reset posistion and fall through for alternative:
 331          position = pos;
 332       }
 333       if(take_second)
 334       {
 335          pstate = rep->alt.p;
 336          return true;
 337       }
 338       return false; // can't take anything, fail...
 339    }
 340    else // non-greedy
 341    {
 342       // try and skip the repeat if we can:
 343       if(take_second)
 344       {
 345          // store position in case we fail:
 346          BidiIterator pos = position;
 347          pstate = rep->alt.p;
 348          if(match_all_states())
 349             return true;
 350          // failed alternative, reset posistion and fall through for repeat:
 351          position = pos;
 352       }
 353       if((next_count->get_count() < rep->max) && take_first)
 354       {
 355          // increase the counter:
 356          ++(*next_count);
 357          pstate = rep->next.p;
 358          return match_all_states();
 359       }
 360    }
 361    return false;
 362 #ifdef BOOST_MSVC
 363 #pragma warning(pop)
 364 #endif
 365 }
 366
 367 template <class BidiIterator, class Allocator, class traits>
 368 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
 369 {
 370 #ifdef BOOST_MSVC
 371 #pragma warning(push)
 372 #pragma warning(disable:4127)
 373 #endif
 374    unsigned count = 0;
 375    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 376    re_syntax_base* psingle = rep->next.p;
 377    // match compulsary repeats first:
 378    while(count < rep->min)
 379    {
 380       pstate = psingle;
 381       if(!match_wild())
 382          return false;
 383       ++count;
 384    }
 385    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 386    if(greedy)
 387    {
 388       // normal repeat:
 389       while(count < rep->max)
 390       {
 391          pstate = psingle;
 392          if(!match_wild())
 393             break;
 394          ++count;
 395       }
 396       if((rep->leading) && (count < rep->max))
 397          restart = position;
 398       pstate = rep;
 399       return backtrack_till_match(count - rep->min);
 400    }
 401    else
 402    {
 403       // non-greedy, keep trying till we get a match:
 404       BidiIterator save_pos;
 405       do
 406       {
 407          if((rep->leading) && (rep->max == UINT_MAX))
 408             restart = position;
 409          pstate = rep->alt.p;
 410          save_pos = position;
 411          ++state_count;
 412          if(match_all_states())
 413             return true;
 414          if(count >= rep->max)
 415             return false;
 416          ++count;
 417          pstate = psingle;
 418          position = save_pos;
 419          if(!match_wild())
 420             return false;
 421       }while(true);
 422    }
 423 #ifdef BOOST_MSVC
 424 #pragma warning(pop)
 425 #endif
 426 }
 427
 428 template <class BidiIterator, class Allocator, class traits>
 429 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
 430 {
 431 #ifdef BOOST_MSVC
 432 #pragma warning(push)
 433 #pragma warning(disable:4127)
 434 #endif
 435    if(m_match_flags & match_not_dot_null)
 436       return match_dot_repeat_slow();
 437    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
 438       return match_dot_repeat_slow();
 439    //
 440    // start by working out how much we can skip:
 441    //
 442    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 443 #ifdef BOOST_MSVC
 444 #pragma warning(push)
 445 #pragma warning(disable:4267)
 446 #endif
 447    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 448    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));
 449    if(rep->min > count)
 450    {
 451       position = last;
 452       return false;  // not enough text left to match
 453    }
 454    std::advance(position, count);
 455 #ifdef BOOST_MSVC
 456 #pragma warning(pop)
 457 #endif
 458    if((rep->leading) && (count < rep->max) && greedy)
 459       restart = position;
 460    if(greedy)
 461       return backtrack_till_match(count - rep->min);
 462
 463    // non-greedy, keep trying till we get a match:
 464    BidiIterator save_pos;
 465    do
 466    {
 467       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 468       {
 469          ++position;
 470          ++count;
 471       }
 472       if((rep->leading) && (rep->max == UINT_MAX))
 473          restart = position;
 474       pstate = rep->alt.p;
 475       save_pos = position;
 476       ++state_count;
 477       if(match_all_states())
 478          return true;
 479       if(count >= rep->max)
 480          return false;
 481       if(position == last)
 482          return false;
 483       position = ++save_pos;
 484       ++count;
 485    }while(true);
 486 #ifdef BOOST_MSVC
 487 #pragma warning(pop)
 488 #endif
 489 }
 490
 491 template <class BidiIterator, class Allocator, class traits>
 492 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
 493 {
 494 #ifdef BOOST_MSVC
 495 #pragma warning(push)
 496 #pragma warning(disable:4127)
 497 #endif
 498 #ifdef __BORLANDC__
 499 #pragma option push -w-8008 -w-8066 -w-8004
 500 #endif
 501    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 502    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
 503    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
 504    unsigned count = 0;
 505    //
 506    // start by working out how much we can skip:
 507    //
 508    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 509    std::size_t desired = greedy ? rep->max : rep->min;
 510    if(::boost::is_random_access_iterator<BidiIterator>::value)
 511    {
 512       BidiIterator end = position;
 513       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 514       BidiIterator origin(position);
 515       while((position != end) && (traits_inst.translate(*position, icase) == what))
 516       {
 517          ++position;
 518       }
 519       count = (unsigned)::boost::re_detail::distance(origin, position);
 520    }
 521    else
 522    {
 523       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
 524       {
 525          ++position;
 526          ++count;
 527       }
 528    }
 529    if((rep->leading) && (count < rep->max) && greedy)
 530       restart = position;
 531    if(count < rep->min)
 532       return false;
 533
 534    if(greedy)
 535       return backtrack_till_match(count - rep->min);
 536
 537    // non-greedy, keep trying till we get a match:
 538    BidiIterator save_pos;
 539    do
 540    {
 541       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 542       {
 543          if((traits_inst.translate(*position, icase) == what))
 544          {
 545             ++position;
 546             ++count;
 547          }
 548          else
 549             return false;  // counldn't repeat even though it was the only option
 550       }
 551       if((rep->leading) && (rep->max == UINT_MAX))
 552          restart = position;
 553       pstate = rep->alt.p;
 554       save_pos = position;
 555       ++state_count;
 556       if(match_all_states())
 557          return true;
 558       if(count >= rep->max)
 559          return false;
 560       if(position == last)
 561          return false;
 562       position = save_pos;
 563       if(traits_inst.translate(*position, icase) == what)
 564       {
 565          ++position;
 566          ++count;
 567       }
 568       else
 569       {
 570          return false;
 571       }
 572    }while(true);
 573 #ifdef __BORLANDC__
 574 #pragma option pop
 575 #endif
 576 #ifdef BOOST_MSVC
 577 #pragma warning(pop)
 578 #endif
 579 }
 580
 581 template <class BidiIterator, class Allocator, class traits>
 582 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
 583 {
 584 #ifdef BOOST_MSVC
 585 #pragma warning(push)
 586 #pragma warning(disable:4127)
 587 #endif
 588 #ifdef __BORLANDC__
 589 #pragma option push -w-8008 -w-8066 -w-8004
 590 #endif
 591    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 592    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
 593    unsigned count = 0;
 594    //
 595    // start by working out how much we can skip:
 596    //
 597    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 598    std::size_t desired = greedy ? rep->max : rep->min;
 599    if(::boost::is_random_access_iterator<BidiIterator>::value)
 600    {
 601       BidiIterator end = position;
 602       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 603       BidiIterator origin(position);
 604       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 605       {
 606          ++position;
 607       }
 608       count = (unsigned)::boost::re_detail::distance(origin, position);
 609    }
 610    else
 611    {
 612       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 613       {
 614          ++position;
 615          ++count;
 616       }
 617    }
 618    if((rep->leading) && (count < rep->max) && greedy)
 619       restart = position;
 620    if(count < rep->min)
 621       return false;
 622
 623    if(greedy)
 624       return backtrack_till_match(count - rep->min);
 625
 626    // non-greedy, keep trying till we get a match:
 627    BidiIterator save_pos;
 628    do
 629    {
 630       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 631       {
 632          if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 633          {
 634             ++position;
 635             ++count;
 636          }
 637          else
 638             return false;  // counldn't repeat even though it was the only option
 639       }
 640       if((rep->leading) && (rep->max == UINT_MAX))
 641          restart = position;
 642       pstate = rep->alt.p;
 643       save_pos = position;
 644       ++state_count;
 645       if(match_all_states())
 646          return true;
 647       if(count >= rep->max)
 648          return false;
 649       if(position == last)
 650          return false;
 651       position = save_pos;
 652       if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 653       {
 654          ++position;
 655          ++count;
 656       }
 657       else
 658       {
 659          return false;
 660       }
 661    }while(true);
 662 #ifdef __BORLANDC__
 663 #pragma option pop
 664 #endif
 665 #ifdef BOOST_MSVC
 666 #pragma warning(pop)
 667 #endif
 668 }
 669
 670 template <class BidiIterator, class Allocator, class traits>
 671 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
 672 {
 673 #ifdef BOOST_MSVC
 674 #pragma warning(push)
 675 #pragma warning(disable:4127)
 676 #endif
 677 #ifdef __BORLANDC__
 678 #pragma option push -w-8008 -w-8066 -w-8004
 679 #endif
 680    typedef typename traits::char_class_type char_class_type;
 681    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 682    const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
 683    unsigned count = 0;
 684    //
 685    // start by working out how much we can skip:
 686    //
 687    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
 688    std::size_t desired = greedy ? rep->max : rep->min;
 689    if(::boost::is_random_access_iterator<BidiIterator>::value)
 690    {
 691       BidiIterator end = position;
 692       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
 693       BidiIterator origin(position);
 694       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 695       {
 696          ++position;
 697       }
 698       count = (unsigned)::boost::re_detail::distance(origin, position);
 699    }
 700    else
 701    {
 702       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
 703       {
 704          ++position;
 705          ++count;
 706       }
 707    }
 708    if((rep->leading) && (count < rep->max) && greedy)
 709       restart = position;
 710    if(count < rep->min)
 711       return false;
 712
 713    if(greedy)
 714       return backtrack_till_match(count - rep->min);
 715
 716    // non-greedy, keep trying till we get a match:
 717    BidiIterator save_pos;
 718    do
 719    {
 720       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
 721       {
 722          if(position != re_is_set_member(position, last, set, re.get_data(), icase))
 723          {
 724             ++position;
 725             ++count;
 726          }
 727          else
 728             return false;  // counldn't repeat even though it was the only option
 729       }
 730       if((rep->leading) && (rep->max == UINT_MAX))
 731          restart = position;
 732       pstate = rep->alt.p;
 733       save_pos = position;
 734       ++state_count;
 735       if(match_all_states())
 736          return true;
 737       if(count >= rep->max)
 738          return false;
 739       if(position == last)
 740          return false;
 741       position = save_pos;
 742       if(position != re_is_set_member(position, last, set, re.get_data(), icase))
 743       {
 744          ++position;
 745          ++count;
 746       }
 747       else
 748       {
 749          return false;
 750       }
 751    }while(true);
 752 #ifdef __BORLANDC__
 753 #pragma option pop
 754 #endif
 755 #ifdef BOOST_MSVC
 756 #pragma warning(pop)
 757 #endif
 758 }
 759
 760 template <class BidiIterator, class Allocator, class traits>
 761 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
 762 {
 763 #ifdef BOOST_MSVC
 764 #pragma warning(push)
 765 #pragma warning(disable:4127)
 766 #endif
 767    if((m_match_flags & match_partial) && (position == last))
 768       m_has_partial_match = true;
 769
 770    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
 771    BidiIterator backtrack = position;
 772    if(position == last)
 773    {
 774       if(rep->can_be_null & mask_skip)
 775       {
 776          pstate = rep->alt.p;
 777          if(match_all_states())
 778             return true;
 779       }
 780       if(count)
 781       {
 782          position = --backtrack;
 783          --count;
 784       }
 785       else
 786          return false;
 787    }
 788    do
 789    {
 790       while(count && !can_start(*position, rep->_map, mask_skip))
 791       {
 792          --position;
 793          --count;
 794          ++state_count;
 795       }
 796       pstate = rep->alt.p;
 797       backtrack = position;
 798       if(match_all_states())
 799          return true;
 800       if(count == 0)
 801          return false;
 802       position = --backtrack;
 803       ++state_count;
 804       --count;
 805    }while(true);
 806 #ifdef BOOST_MSVC
 807 #pragma warning(pop)
 808 #endif
 809 }
 810
 811 } // namespace re_detail
 812 } // namespace boost
 813
 814 #ifdef BOOST_HAS_ABI_HEADERS
 815 #  include BOOST_ABI_SUFFIX
 816 #endif
 817
 818 #endif
 819