ceph/src/boost/libs/regex/include/boost/regex/v4/perl_matcher_common.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   *                common to both the recursive and non-recursive versions.
  18   */
  19
  20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
  21 #define BOOST_REGEX_V4_PERL_MATCHER_COMMON_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 __BORLANDC__
  35 #  pragma option push -w-8008 -w-8066
  36 #endif
  37 #ifdef BOOST_MSVC
  38 #  pragma warning(push)
  39 #  pragma warning(disable: 4800)
  40 #endif
  41
  42 namespace boost{
  43 namespace BOOST_REGEX_DETAIL_NS{
  44
  45 template <class BidiIterator, class Allocator, class traits>
  46 void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)
  47 {
  48    typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;
  49    typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;
  50
  51    if(e.empty())
  52    {
  53       // precondition failure: e is not a valid regex.
  54       std::invalid_argument ex("Invalid regular expression object");
  55       boost::throw_exception(ex);
  56    }
  57    pstate = 0;
  58    m_match_flags = f;
  59    estimate_max_state_count(static_cast<category*>(0));
  60    expression_flag_type re_f = re.flags();
  61    icase = re_f & regex_constants::icase;
  62    if(!(m_match_flags & (match_perl|match_posix)))
  63    {
  64       if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
  65          m_match_flags |= match_perl;
  66       else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
  67          m_match_flags |= match_perl;
  68       else if((re_f & (regbase::main_option_type|regbase::literal)) == (regbase::literal))
  69          m_match_flags |= match_perl;
  70       else
  71          m_match_flags |= match_posix;
  72    }
  73    if(m_match_flags & match_posix)
  74    {
  75       m_temp_match.reset(new match_results<BidiIterator, Allocator>());
  76       m_presult = m_temp_match.get();
  77    }
  78    else
  79       m_presult = &m_result;
  80 #ifdef BOOST_REGEX_NON_RECURSIVE
  81    m_stack_base = 0;
  82    m_backup_state = 0;
  83 #elif defined(BOOST_REGEX_RECURSIVE)
  84    m_can_backtrack = true;
  85    m_have_accept = false;
  86 #endif
  87    // find the value to use for matching word boundaries:
  88    m_word_mask = re.get_data().m_word_mask;
  89    // find bitmask to use for matching '.':
  90    match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? BOOST_REGEX_DETAIL_NS::test_not_newline : BOOST_REGEX_DETAIL_NS::test_newline);
  91    // Disable match_any if requested in the state machine:
  92    if(e.get_data().m_disable_match_any)
  93       m_match_flags &= ~regex_constants::match_any;
  94 }
  95
  96 template <class BidiIterator, class Allocator, class traits>
  97 void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)
  98 {
  99    //
 100    // How many states should we allow our machine to visit before giving up?
 101    // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)
 102    // where N is the length of the string, and S is the number of states
 103    // in the machine.  It's tempting to up this to O(N^2S) or even O(N^2S^2)
 104    // but these take unreasonably amounts of time to bale out in pathological
 105    // cases.
 106    //
 107    // Calculate NS^2 first:
 108    //
 109    static const std::ptrdiff_t k = 100000;
 110    std::ptrdiff_t dist = boost::BOOST_REGEX_DETAIL_NS::distance(base, last);
 111    if(dist == 0)
 112       dist = 1;
 113    std::ptrdiff_t states = re.size();
 114    if(states == 0)
 115       states = 1;
 116    states *= states;
 117    if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
 118    {
 119       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 120       return;
 121    }
 122    states *= dist;
 123    if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
 124    {
 125       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 126       return;
 127    }
 128    states += k;
 129
 130    max_state_count = states;
 131
 132    //
 133    // Now calculate N^2:
 134    //
 135    states = dist;
 136    if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
 137    {
 138       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 139       return;
 140    }
 141    states *= dist;
 142    if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
 143    {
 144       max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 145       return;
 146    }
 147    states += k;
 148    //
 149    // N^2 can be a very large number indeed, to prevent things getting out
 150    // of control, cap the max states:
 151    //
 152    if(states > BOOST_REGEX_MAX_STATE_COUNT)
 153       states = BOOST_REGEX_MAX_STATE_COUNT;
 154    //
 155    // If (the possibly capped) N^2 is larger than our first estimate,
 156    // use this instead:
 157    //
 158    if(states > max_state_count)
 159       max_state_count = states;
 160 }
 161
 162 template <class BidiIterator, class Allocator, class traits>
 163 inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
 164 {
 165    // we don't know how long the sequence is:
 166    max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
 167 }
 168
 169 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
 170 template <class BidiIterator, class Allocator, class traits>
 171 inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
 172    protected_proc_type proc)
 173 {
 174    ::boost::BOOST_REGEX_DETAIL_NS::concrete_protected_call
 175       <perl_matcher<BidiIterator, Allocator, traits> >
 176       obj(this, proc);
 177    return obj.execute();
 178
 179 }
 180 #endif
 181
 182 template <class BidiIterator, class Allocator, class traits>
 183 inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
 184 {
 185 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
 186    return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
 187 #else
 188    return match_imp();
 189 #endif
 190 }
 191
 192 template <class BidiIterator, class Allocator, class traits>
 193 bool perl_matcher<BidiIterator, Allocator, traits>::match_imp()
 194 {
 195    // initialise our stack if we are non-recursive:
 196 #ifdef BOOST_REGEX_NON_RECURSIVE
 197    save_state_init init(&m_stack_base, &m_backup_state);
 198    used_block_count = BOOST_REGEX_MAX_BLOCKS;
 199 #if !defined(BOOST_NO_EXCEPTIONS)
 200    try{
 201 #endif
 202 #endif
 203
 204    // reset our state machine:
 205    position = base;
 206    search_base = base;
 207    state_count = 0;
 208    m_match_flags |= regex_constants::match_all;
 209    m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), search_base, last);
 210    m_presult->set_base(base);
 211    m_presult->set_named_subs(this->re.get_named_subs());
 212    if(m_match_flags & match_posix)
 213       m_result = *m_presult;
 214    verify_options(re.flags(), m_match_flags);
 215    if(0 == match_prefix())
 216       return false;
 217    return (m_result[0].second == last) && (m_result[0].first == base);
 218
 219 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
 220    }
 221    catch(...)
 222    {
 223       // unwind all pushed states, apart from anything else this
 224       // ensures that all the states are correctly destructed
 225       // not just the memory freed.
 226       while(unwind(true)){}
 227       throw;
 228    }
 229 #endif
 230 }
 231
 232 template <class BidiIterator, class Allocator, class traits>
 233 inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
 234 {
 235 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
 236    return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
 237 #else
 238    return find_imp();
 239 #endif
 240 }
 241
 242 template <class BidiIterator, class Allocator, class traits>
 243 bool perl_matcher<BidiIterator, Allocator, traits>::find_imp()
 244 {
 245    static matcher_proc_type const s_find_vtable[7] =
 246    {
 247       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_any,
 248       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_word,
 249       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_line,
 250       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf,
 251       &perl_matcher<BidiIterator, Allocator, traits>::match_prefix,
 252       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
 253       &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
 254    };
 255
 256    // initialise our stack if we are non-recursive:
 257 #ifdef BOOST_REGEX_NON_RECURSIVE
 258    save_state_init init(&m_stack_base, &m_backup_state);
 259    used_block_count = BOOST_REGEX_MAX_BLOCKS;
 260 #if !defined(BOOST_NO_EXCEPTIONS)
 261    try{
 262 #endif
 263 #endif
 264
 265    state_count = 0;
 266    if((m_match_flags & regex_constants::match_init) == 0)
 267    {
 268       // reset our state machine:
 269       search_base = position = base;
 270       pstate = re.get_first_state();
 271       m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), base, last);
 272       m_presult->set_base(base);
 273       m_presult->set_named_subs(this->re.get_named_subs());
 274       m_match_flags |= regex_constants::match_init;
 275    }
 276    else
 277    {
 278       // start again:
 279       search_base = position = m_result[0].second;
 280       // If last match was null and match_not_null was not set then increment
 281       // our start position, otherwise we go into an infinite loop:
 282       if(((m_match_flags & match_not_null) == 0) && (m_result.length() == 0))
 283       {
 284          if(position == last)
 285             return false;
 286          else
 287             ++position;
 288       }
 289       // reset $` start:
 290       m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), search_base, last);
 291       //if((base != search_base) && (base == backstop))
 292       //   m_match_flags |= match_prev_avail;
 293    }
 294    if(m_match_flags & match_posix)
 295    {
 296       m_result.set_size(static_cast<typename results_type::size_type>(1u + re.mark_count()), base, last);
 297       m_result.set_base(base);
 298    }
 299
 300    verify_options(re.flags(), m_match_flags);
 301    // find out what kind of expression we have:
 302    unsigned type = (m_match_flags & match_continuous) ?
 303       static_cast<unsigned int>(regbase::restart_continue)
 304          : static_cast<unsigned int>(re.get_restart_type());
 305
 306    // call the appropriate search routine:
 307    matcher_proc_type proc = s_find_vtable[type];
 308    return (this->*proc)();
 309
 310 #if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
 311    }
 312    catch(...)
 313    {
 314       // unwind all pushed states, apart from anything else this
 315       // ensures that all the states are correctly destructed
 316       // not just the memory freed.
 317       while(unwind(true)){}
 318       throw;
 319    }
 320 #endif
 321 }
 322
 323 template <class BidiIterator, class Allocator, class traits>
 324 bool perl_matcher<BidiIterator, Allocator, traits>::match_prefix()
 325 {
 326    m_has_partial_match = false;
 327    m_has_found_match = false;
 328    pstate = re.get_first_state();
 329    m_presult->set_first(position);
 330    restart = position;
 331    match_all_states();
 332    if(!m_has_found_match && m_has_partial_match && (m_match_flags & match_partial))
 333    {
 334       m_has_found_match = true;
 335       m_presult->set_second(last, 0, false);
 336       position = last;
 337       if((m_match_flags & match_posix) == match_posix)
 338       {
 339          m_result.maybe_assign(*m_presult);
 340       }
 341    }
 342 #ifdef BOOST_REGEX_MATCH_EXTRA
 343    if(m_has_found_match && (match_extra & m_match_flags))
 344    {
 345       //
 346       // we have a match, reverse the capture information:
 347       //
 348       for(unsigned i = 0; i < m_presult->size(); ++i)
 349       {
 350          typename sub_match<BidiIterator>::capture_sequence_type & seq = ((*m_presult)[i]).get_captures();
 351          std::reverse(seq.begin(), seq.end());
 352       }
 353    }
 354 #endif
 355    if(!m_has_found_match)
 356       position = restart; // reset search postion
 357 #ifdef BOOST_REGEX_RECURSIVE
 358    m_can_backtrack = true; // reset for further searches
 359 #endif
 360    return m_has_found_match;
 361 }
 362
 363 template <class BidiIterator, class Allocator, class traits>
 364 bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
 365 {
 366    unsigned int len = static_cast<const re_literal*>(pstate)->length;
 367    const char_type* what = reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
 368    //
 369    // compare string with what we stored in
 370    // our records:
 371    for(unsigned int i = 0; i < len; ++i, ++position)
 372    {
 373       if((position == last) || (traits_inst.translate(*position, icase) != what[i]))
 374          return false;
 375    }
 376    pstate = pstate->next.p;
 377    return true;
 378 }
 379
 380 template <class BidiIterator, class Allocator, class traits>
 381 bool perl_matcher<BidiIterator, Allocator, traits>::match_start_line()
 382 {
 383    if(position == backstop)
 384    {
 385       if((m_match_flags & match_prev_avail) == 0)
 386       {
 387          if((m_match_flags & match_not_bol) == 0)
 388          {
 389             pstate = pstate->next.p;
 390             return true;
 391          }
 392          return false;
 393       }
 394    }
 395    else if(m_match_flags & match_single_line)
 396       return false;
 397
 398    // check the previous value character:
 399    BidiIterator t(position);
 400    --t;
 401    if(position != last)
 402    {
 403       if(is_separator(*t) && !((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n'))) )
 404       {
 405          pstate = pstate->next.p;
 406          return true;
 407       }
 408    }
 409    else if(is_separator(*t))
 410    {
 411       pstate = pstate->next.p;
 412       return true;
 413    }
 414    return false;
 415 }
 416
 417 template <class BidiIterator, class Allocator, class traits>
 418 bool perl_matcher<BidiIterator, Allocator, traits>::match_end_line()
 419 {
 420    if(position != last)
 421    {
 422       if(m_match_flags & match_single_line)
 423          return false;
 424       // we're not yet at the end so *first is always valid:
 425       if(is_separator(*position))
 426       {
 427          if((position != backstop) || (m_match_flags & match_prev_avail))
 428          {
 429             // check that we're not in the middle of \r\n sequence
 430             BidiIterator t(position);
 431             --t;
 432             if((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n')))
 433             {
 434                return false;
 435             }
 436          }
 437          pstate = pstate->next.p;
 438          return true;
 439       }
 440    }
 441    else if((m_match_flags & match_not_eol) == 0)
 442    {
 443       pstate = pstate->next.p;
 444       return true;
 445    }
 446    return false;
 447 }
 448
 449 template <class BidiIterator, class Allocator, class traits>
 450 bool perl_matcher<BidiIterator, Allocator, traits>::match_wild()
 451 {
 452    if(position == last)
 453       return false;
 454    if(is_separator(*position) && ((match_any_mask & static_cast<const re_dot*>(pstate)->mask) == 0))
 455       return false;
 456    if((*position == char_type(0)) && (m_match_flags & match_not_dot_null))
 457       return false;
 458    pstate = pstate->next.p;
 459    ++position;
 460    return true;
 461 }
 462
 463 template <class BidiIterator, class Allocator, class traits>
 464 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
 465 {
 466    bool b; // indcates whether next character is a word character
 467    if(position != last)
 468    {
 469       // prev and this character must be opposites:
 470       b = traits_inst.isctype(*position, m_word_mask);
 471    }
 472    else
 473    {
 474       b = (m_match_flags & match_not_eow) ? true : false;
 475    }
 476    if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
 477    {
 478       if(m_match_flags & match_not_bow)
 479          b ^= true;
 480       else
 481          b ^= false;
 482    }
 483    else
 484    {
 485       --position;
 486       b ^= traits_inst.isctype(*position, m_word_mask);
 487       ++position;
 488    }
 489    if(b)
 490    {
 491       pstate = pstate->next.p;
 492       return true;
 493    }
 494    return false; // no match if we get to here...
 495 }
 496
 497 template <class BidiIterator, class Allocator, class traits>
 498 bool perl_matcher<BidiIterator, Allocator, traits>::match_within_word()
 499 {
 500    if(position == last)
 501       return false;
 502    // both prev and this character must be m_word_mask:
 503    bool prev = traits_inst.isctype(*position, m_word_mask);
 504    {
 505       bool b;
 506       if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
 507          return false;
 508       else
 509       {
 510          --position;
 511          b = traits_inst.isctype(*position, m_word_mask);
 512          ++position;
 513       }
 514       if(b == prev)
 515       {
 516          pstate = pstate->next.p;
 517          return true;
 518       }
 519    }
 520    return false;
 521 }
 522
 523 template <class BidiIterator, class Allocator, class traits>
 524 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_start()
 525 {
 526    if(position == last)
 527       return false; // can't be starting a word if we're already at the end of input
 528    if(!traits_inst.isctype(*position, m_word_mask))
 529       return false; // next character isn't a word character
 530    if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
 531    {
 532       if(m_match_flags & match_not_bow)
 533          return false; // no previous input
 534    }
 535    else
 536    {
 537       // otherwise inside buffer:
 538       BidiIterator t(position);
 539       --t;
 540       if(traits_inst.isctype(*t, m_word_mask))
 541          return false; // previous character not non-word
 542    }
 543    // OK we have a match:
 544    pstate = pstate->next.p;
 545    return true;
 546 }
 547
 548 template <class BidiIterator, class Allocator, class traits>
 549 bool perl_matcher<BidiIterator, Allocator, traits>::match_word_end()
 550 {
 551    if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
 552       return false;  // start of buffer can't be end of word
 553    BidiIterator t(position);
 554    --t;
 555    if(traits_inst.isctype(*t, m_word_mask) == false)
 556       return false;  // previous character wasn't a word character
 557
 558    if(position == last)
 559    {
 560       if(m_match_flags & match_not_eow)
 561          return false; // end of buffer but not end of word
 562    }
 563    else
 564    {
 565       // otherwise inside buffer:
 566       if(traits_inst.isctype(*position, m_word_mask))
 567          return false; // next character is a word character
 568    }
 569    pstate = pstate->next.p;
 570    return true;      // if we fall through to here then we've succeeded
 571 }
 572
 573 template <class BidiIterator, class Allocator, class traits>
 574 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start()
 575 {
 576    if((position != backstop) || (m_match_flags & match_not_bob))
 577       return false;
 578    // OK match:
 579    pstate = pstate->next.p;
 580    return true;
 581 }
 582
 583 template <class BidiIterator, class Allocator, class traits>
 584 bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end()
 585 {
 586    if((position != last) || (m_match_flags & match_not_eob))
 587       return false;
 588    // OK match:
 589    pstate = pstate->next.p;
 590    return true;
 591 }
 592
 593 template <class BidiIterator, class Allocator, class traits>
 594 bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
 595 {
 596    //
 597    // Compare with what we previously matched.
 598    // Note that this succeeds if the backref did not partisipate
 599    // in the match, this is in line with ECMAScript, but not Perl
 600    // or PCRE.
 601    //
 602    int index = static_cast<const re_brace*>(pstate)->index;
 603    if(index >= 10000)
 604    {
 605       named_subexpressions::range_type r = re.get_data().equal_range(index);
 606       BOOST_ASSERT(r.first != r.second);
 607       do
 608       {
 609          index = r.first->index;
 610          ++r.first;
 611       }while((r.first != r.second) && ((*m_presult)[index].matched != true));
 612    }
 613
 614    if((m_match_flags & match_perl) && !(*m_presult)[index].matched)
 615       return false;
 616
 617    BidiIterator i = (*m_presult)[index].first;
 618    BidiIterator j = (*m_presult)[index].second;
 619    while(i != j)
 620    {
 621       if((position == last) || (traits_inst.translate(*position, icase) != traits_inst.translate(*i, icase)))
 622          return false;
 623       ++i;
 624       ++position;
 625    }
 626    pstate = pstate->next.p;
 627    return true;
 628 }
 629
 630 template <class BidiIterator, class Allocator, class traits>
 631 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set()
 632 {
 633    typedef typename traits::char_class_type char_class_type;
 634    // let the traits class do the work:
 635    if(position == last)
 636       return false;
 637    BidiIterator t = re_is_set_member(position, last, static_cast<const re_set_long<char_class_type>*>(pstate), re.get_data(), icase);
 638    if(t != position)
 639    {
 640       pstate = pstate->next.p;
 641       position = t;
 642       return true;
 643    }
 644    return false;
 645 }
 646
 647 template <class BidiIterator, class Allocator, class traits>
 648 bool perl_matcher<BidiIterator, Allocator, traits>::match_set()
 649 {
 650    if(position == last)
 651       return false;
 652    if(static_cast<const re_set*>(pstate)->_map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
 653    {
 654       pstate = pstate->next.p;
 655       ++position;
 656       return true;
 657    }
 658    return false;
 659 }
 660
 661 template <class BidiIterator, class Allocator, class traits>
 662 bool perl_matcher<BidiIterator, Allocator, traits>::match_jump()
 663 {
 664    pstate = static_cast<const re_jump*>(pstate)->alt.p;
 665    return true;
 666 }
 667
 668 template <class BidiIterator, class Allocator, class traits>
 669 bool perl_matcher<BidiIterator, Allocator, traits>::match_combining()
 670 {
 671    if(position == last)
 672       return false;
 673    if(is_combining(traits_inst.translate(*position, icase)))
 674       return false;
 675    ++position;
 676    while((position != last) && is_combining(traits_inst.translate(*position, icase)))
 677       ++position;
 678    pstate = pstate->next.p;
 679    return true;
 680 }
 681
 682 template <class BidiIterator, class Allocator, class traits>
 683 bool perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end()
 684 {
 685    if(m_match_flags & match_not_eob)
 686       return false;
 687    BidiIterator p(position);
 688    while((p != last) && is_separator(traits_inst.translate(*p, icase)))++p;
 689    if(p != last)
 690       return false;
 691    pstate = pstate->next.p;
 692    return true;
 693 }
 694
 695 template <class BidiIterator, class Allocator, class traits>
 696 bool perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue()
 697 {
 698    if(position == search_base)
 699    {
 700       pstate = pstate->next.p;
 701       return true;
 702    }
 703    return false;
 704 }
 705
 706 template <class BidiIterator, class Allocator, class traits>
 707 bool perl_matcher<BidiIterator, Allocator, traits>::match_backstep()
 708 {
 709 #ifdef BOOST_MSVC
 710 #pragma warning(push)
 711 #pragma warning(disable:4127)
 712 #endif
 713    if( ::boost::is_random_access_iterator<BidiIterator>::value)
 714    {
 715       std::ptrdiff_t maxlen = ::boost::BOOST_REGEX_DETAIL_NS::distance(backstop, position);
 716       if(maxlen < static_cast<const re_brace*>(pstate)->index)
 717          return false;
 718       std::advance(position, -static_cast<const re_brace*>(pstate)->index);
 719    }
 720    else
 721    {
 722       int c = static_cast<const re_brace*>(pstate)->index;
 723       while(c--)
 724       {
 725          if(position == backstop)
 726             return false;
 727          --position;
 728       }
 729    }
 730    pstate = pstate->next.p;
 731    return true;
 732 #ifdef BOOST_MSVC
 733 #pragma warning(pop)
 734 #endif
 735 }
 736
 737 template <class BidiIterator, class Allocator, class traits>
 738 inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
 739 {
 740    // return true if marked sub-expression N has been matched:
 741    int index = static_cast<const re_brace*>(pstate)->index;
 742    bool result = false;
 743    if(index == 9999)
 744    {
 745       // Magic value for a (DEFINE) block:
 746       return false;
 747    }
 748    else if(index > 0)
 749    {
 750       // Have we matched subexpression "index"?
 751       // Check if index is a hash value:
 752       if(index >= 10000)
 753       {
 754          named_subexpressions::range_type r = re.get_data().equal_range(index);
 755          while(r.first != r.second)
 756          {
 757             if((*m_presult)[r.first->index].matched)
 758             {
 759                result = true;
 760                break;
 761             }
 762             ++r.first;
 763          }
 764       }
 765       else
 766       {
 767          result = (*m_presult)[index].matched;
 768       }
 769       pstate = pstate->next.p;
 770    }
 771    else
 772    {
 773       // Have we recursed into subexpression "index"?
 774       // If index == 0 then check for any recursion at all, otherwise for recursion to -index-1.
 775       int idx = -index-1;
 776       if(idx >= 10000)
 777       {
 778          named_subexpressions::range_type r = re.get_data().equal_range(idx);
 779          int stack_index = recursion_stack.empty() ? -1 : recursion_stack.back().idx;
 780          while(r.first != r.second)
 781          {
 782             result |= (stack_index == r.first->index);
 783             if(result)break;
 784             ++r.first;
 785          }
 786       }
 787       else
 788       {
 789          result = !recursion_stack.empty() && ((recursion_stack.back().idx == idx) || (index == 0));
 790       }
 791       pstate = pstate->next.p;
 792    }
 793    return result;
 794 }
 795
 796 template <class BidiIterator, class Allocator, class traits>
 797 bool perl_matcher<BidiIterator, Allocator, traits>::match_fail()
 798 {
 799    // Just force a backtrack:
 800    return false;
 801 }
 802
 803 template <class BidiIterator, class Allocator, class traits>
 804 bool perl_matcher<BidiIterator, Allocator, traits>::match_accept()
 805 {
 806    if(!recursion_stack.empty())
 807    {
 808       return skip_until_paren(recursion_stack.back().idx);
 809    }
 810    else
 811    {
 812       return skip_until_paren(INT_MAX);
 813    }
 814 }
 815
 816 template <class BidiIterator, class Allocator, class traits>
 817 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_any()
 818 {
 819 #ifdef BOOST_MSVC
 820 #pragma warning(push)
 821 #pragma warning(disable:4127)
 822 #endif
 823    const unsigned char* _map = re.get_map();
 824    while(true)
 825    {
 826       // skip everything we can't match:
 827       while((position != last) && !can_start(*position, _map, (unsigned char)mask_any) )
 828          ++position;
 829       if(position == last)
 830       {
 831          // run out of characters, try a null match if possible:
 832          if(re.can_be_null())
 833             return match_prefix();
 834          break;
 835       }
 836       // now try and obtain a match:
 837       if(match_prefix())
 838          return true;
 839       if(position == last)
 840          return false;
 841       ++position;
 842    }
 843    return false;
 844 #ifdef BOOST_MSVC
 845 #pragma warning(pop)
 846 #endif
 847 }
 848
 849 template <class BidiIterator, class Allocator, class traits>
 850 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_word()
 851 {
 852 #ifdef BOOST_MSVC
 853 #pragma warning(push)
 854 #pragma warning(disable:4127)
 855 #endif
 856    // do search optimised for word starts:
 857    const unsigned char* _map = re.get_map();
 858    if((m_match_flags & match_prev_avail) || (position != base))
 859       --position;
 860    else if(match_prefix())
 861       return true;
 862    do
 863    {
 864       while((position != last) && traits_inst.isctype(*position, m_word_mask))
 865          ++position;
 866       while((position != last) && !traits_inst.isctype(*position, m_word_mask))
 867          ++position;
 868       if(position == last)
 869          break;
 870
 871       if(can_start(*position, _map, (unsigned char)mask_any) )
 872       {
 873          if(match_prefix())
 874             return true;
 875       }
 876       if(position == last)
 877          break;
 878    } while(true);
 879    return false;
 880 #ifdef BOOST_MSVC
 881 #pragma warning(pop)
 882 #endif
 883 }
 884
 885 template <class BidiIterator, class Allocator, class traits>
 886 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_line()
 887 {
 888    // do search optimised for line starts:
 889    const unsigned char* _map = re.get_map();
 890    if(match_prefix())
 891       return true;
 892    while(position != last)
 893    {
 894       while((position != last) && !is_separator(*position))
 895          ++position;
 896       if(position == last)
 897          return false;
 898       ++position;
 899       if(position == last)
 900       {
 901          if(re.can_be_null() && match_prefix())
 902             return true;
 903          return false;
 904       }
 905
 906       if( can_start(*position, _map, (unsigned char)mask_any) )
 907       {
 908          if(match_prefix())
 909             return true;
 910       }
 911       if(position == last)
 912          return false;
 913       //++position;
 914    }
 915    return false;
 916 }
 917
 918 template <class BidiIterator, class Allocator, class traits>
 919 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf()
 920 {
 921    if((position == base) && ((m_match_flags & match_not_bob) == 0))
 922       return match_prefix();
 923    return false;
 924 }
 925
 926 template <class BidiIterator, class Allocator, class traits>
 927 bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit()
 928 {
 929 #if 0
 930    if(position == last)
 931       return false; // can't possibly match if we're at the end already
 932
 933    unsigned type = (m_match_flags & match_continuous) ?
 934       static_cast<unsigned int>(regbase::restart_continue)
 935          : static_cast<unsigned int>(re.get_restart_type());
 936
 937    const kmp_info<char_type>* info = access::get_kmp(re);
 938    int len = info->len;
 939    const char_type* x = info->pstr;
 940    int j = 0;
 941    while (position != last)
 942    {
 943       while((j > -1) && (x[j] != traits_inst.translate(*position, icase)))
 944          j = info->kmp_next[j];
 945       ++position;
 946       ++j;
 947       if(j >= len)
 948       {
 949          if(type == regbase::restart_fixed_lit)
 950          {
 951             std::advance(position, -j);
 952             restart = position;
 953             std::advance(restart, len);
 954             m_result.set_first(position);
 955             m_result.set_second(restart);
 956             position = restart;
 957             return true;
 958          }
 959          else
 960          {
 961             restart = position;
 962             std::advance(position, -j);
 963             if(match_prefix())
 964                return true;
 965             else
 966             {
 967                for(int k = 0; (restart != position) && (k < j); ++k, --restart)
 968                      {} // dwa 10/20/2000 - warning suppression for MWCW
 969                if(restart != last)
 970                   ++restart;
 971                position = restart;
 972                j = 0;  //we could do better than this...
 973             }
 974          }
 975       }
 976    }
 977    if((m_match_flags & match_partial) && (position == last) && j)
 978    {
 979       // we need to check for a partial match:
 980       restart = position;
 981       std::advance(position, -j);
 982       return match_prefix();
 983    }
 984 #endif
 985    return false;
 986 }
 987
 988 } // namespace BOOST_REGEX_DETAIL_NS
 989
 990 } // namespace boost
 991
 992 #ifdef BOOST_MSVC
 993 #  pragma warning(pop)
 994 #endif
 995
 996 #ifdef __BORLANDC__
 997 #  pragma option pop
 998 #endif
 999 #ifdef BOOST_MSVC
1000 #pragma warning(push)
1001 #pragma warning(disable: 4103)
1002 #endif
1003 #ifdef BOOST_HAS_ABI_HEADERS
1004 #  include BOOST_ABI_SUFFIX
1005 #endif
1006 #ifdef BOOST_MSVC
1007 #pragma warning(pop)
1008 #endif
1009
1010 #endif
1011