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