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