1 /*

     2  *

     3  * Copyright (c) 2002

     4  * John Maddock

     5  *

     6  * Use, modification and distribution are subject to the 

     7  * Boost Software License, Version 1.0. (See accompanying file 

     8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

     9  *

    10  */

    11 

    12  /*

    13   *   LOCATION:    see http://www.boost.org for most recent version.

    14   *   FILE         perl_matcher_common.cpp

    15   *   VERSION      see <boost/version.hpp>

    16   *   DESCRIPTION: Definitions of perl_matcher member functions that are 

    17   *                specific to the non-recursive implementation.

    18   */

    19 

    20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP

    21 #define BOOST_REGEX_V4_PERL_MATCHER_NON_RECURSIVE_HPP

    22 

    23 #include <new>

    24 

    25 #ifdef BOOST_MSVC

    26 #pragma warning(push)

    27 #pragma warning(disable: 4103)

    28 #endif

    29 #ifdef BOOST_HAS_ABI_HEADERS

    30 #  include BOOST_ABI_PREFIX

    31 #endif

    32 #ifdef BOOST_MSVC

    33 #pragma warning(pop)

    34 #endif

    35 #ifdef BOOST_MSVC

    36 #  pragma warning(push)

    37 #  pragma warning(disable: 4800)

    38 #endif

    39 

    40 namespace boost{

    41 namespace re_detail{

    42 

    43 template <class T>

    44 inline void inplace_destroy(T* p)

    45 {

    46    (void)p;  // warning suppression

    47    p->~T();

    48 }

    49 

    50 struct saved_state

    51 {

    52    union{

    53       unsigned int state_id;

    54       // this padding ensures correct alignment on 64-bit platforms:

    55       std::size_t padding1;

    56       std::ptrdiff_t padding2;

    57       void* padding3;

    58    };

    59    saved_state(unsigned i) : state_id(i) {}

    60 };

    61 

    62 template <class BidiIterator>

    63 struct saved_matched_paren : public saved_state

    64 {

    65    int index;

    66    sub_match<BidiIterator> sub;

    67    saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){};

    68 };

    69 

    70 template <class BidiIterator>

    71 struct saved_position : public saved_state

    72 {

    73    const re_syntax_base* pstate;

    74    BidiIterator position;

    75    saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){};

    76 };

    77 

    78 template <class BidiIterator>

    79 struct saved_assertion : public saved_position<BidiIterator>

    80 {

    81    bool positive;

    82    saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos) 

    83       : saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){};

    84 };

    85 

    86 template <class BidiIterator>

    87 struct saved_repeater : public saved_state

    88 {

    89    repeater_count<BidiIterator> count;

    90    saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start) 

    91       : saved_state(saved_state_repeater_count), count(i,s,start){}

    92 };

    93 

    94 struct saved_extra_block : public saved_state

    95 {

    96    saved_state *base, *end;

    97    saved_extra_block(saved_state* b, saved_state* e) 

    98       : saved_state(saved_state_extra_block), base(b), end(e) {}

    99 };

   100 

   101 struct save_state_init

   102 {

   103    saved_state** stack;

   104    save_state_init(saved_state** base, saved_state** end)

   105       : stack(base)

   106    {

   107       *base = static_cast<saved_state*>(get_mem_block());

   108       *end = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(*base)+BOOST_REGEX_BLOCKSIZE);

   109       --(*end);

   110       (void) new (*end)saved_state(0);

   111       BOOST_ASSERT(*end > *base);

   112    }

   113    ~save_state_init()

   114    {

   115       put_mem_block(*stack);

   116       *stack = 0;

   117    }

   118 };

   119 

   120 template <class BidiIterator>

   121 struct saved_single_repeat : public saved_state

   122 {

   123    std::size_t count;

   124    const re_repeat* rep;

   125    BidiIterator last_position;

   126    saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id) 

   127       : saved_state(arg_id), count(c), rep(r), last_position(lp){}

   128 };

   129 

   130 template <class BidiIterator, class Allocator, class traits>

   131 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()

   132 {

   133    static matcher_proc_type const s_match_vtable[29] = 

   134    {

   135       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),

   136       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,

   137       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,

   138       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,

   139       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,

   140       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,

   141       &perl_matcher<BidiIterator, Allocator, traits>::match_match,

   142       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,

   143       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,

   144       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,

   145       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,

   146       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,

   147       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,

   148       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,

   149       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,

   150       &perl_matcher<BidiIterator, Allocator, traits>::match_set,

   151       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,

   152       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,

   153       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,

   154       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,

   155       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,

   156       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,

   157       (::boost::is_random_access_iterator<BidiIterator>::value ? &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast : &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow),

   158       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,

   159       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,

   160       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,

   161       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,

   162       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,

   163       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,

   164    };

   165 

   166    push_recursion_stopper();

   167    do{

   168       while(pstate)

   169       {

   170          matcher_proc_type proc = s_match_vtable[pstate->type];

   171          ++state_count;

   172          if(!(this->*proc)())

   173          {

   174             if(state_count > max_state_count)

   175                raise_error(traits_inst, regex_constants::error_space);

   176             if((m_match_flags & match_partial) && (position == last) && (position != search_base))

   177                m_has_partial_match = true;

   178             bool successful_unwind = unwind(false);

   179             if((m_match_flags & match_partial) && (position == last) && (position != search_base))

   180                m_has_partial_match = true;

   181             if(false == successful_unwind)

   182                return m_recursive_result;

   183          }

   184       }

   185    }while(unwind(true));

   186    return m_recursive_result;

   187 }

   188 

   189 template <class BidiIterator, class Allocator, class traits>

   190 void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()

   191 {

   192    if(used_block_count)

   193    {

   194       --used_block_count;

   195       saved_state* stack_base;

   196       saved_state* backup_state;

   197       stack_base = static_cast<saved_state*>(get_mem_block());

   198       backup_state = reinterpret_cast<saved_state*>(reinterpret_cast<char*>(stack_base)+BOOST_REGEX_BLOCKSIZE);

   199       saved_extra_block* block = static_cast<saved_extra_block*>(backup_state);

   200       --block;

   201       (void) new (block) saved_extra_block(m_stack_base, m_backup_state);

   202       m_stack_base = stack_base;

   203       m_backup_state = block;

   204    }

   205    else

   206       raise_error(traits_inst, regex_constants::error_size);

   207 }

   208 

   209 template <class BidiIterator, class Allocator, class traits>

   210 inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)

   211 {

   212    BOOST_ASSERT(index);

   213    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);

   214    --pmp;

   215    if(pmp < m_stack_base)

   216    {

   217       extend_stack();

   218       pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);

   219       --pmp;

   220    }

   221    (void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);

   222    m_backup_state = pmp;

   223 }

   224 

   225 template <class BidiIterator, class Allocator, class traits>

   226 inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()

   227 {

   228    saved_state* pmp = m_backup_state;

   229    --pmp;

   230    if(pmp < m_stack_base)

   231    {

   232       extend_stack();

   233       pmp = m_backup_state;

   234       --pmp;

   235    }

   236    (void) new (pmp)saved_state(saved_type_recurse);

   237    m_backup_state = pmp;

   238 }

   239 

   240 template <class BidiIterator, class Allocator, class traits>

   241 inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)

   242 {

   243    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);

   244    --pmp;

   245    if(pmp < m_stack_base)

   246    {

   247       extend_stack();

   248       pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);

   249       --pmp;

   250    }

   251    (void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);

   252    m_backup_state = pmp;

   253 }

   254 

   255 template <class BidiIterator, class Allocator, class traits>

   256 inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)

   257 {

   258    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);

   259    --pmp;

   260    if(pmp < m_stack_base)

   261    {

   262       extend_stack();

   263       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);

   264       --pmp;

   265    }

   266    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);

   267    m_backup_state = pmp;

   268 }

   269 

   270 template <class BidiIterator, class Allocator, class traits>

   271 inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)

   272 {

   273    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);

   274    --pmp;

   275    if(pmp < m_stack_base)

   276    {

   277       extend_stack();

   278       pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);

   279       --pmp;

   280    }

   281    (void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);

   282    m_backup_state = pmp;

   283 }

   284 

   285 template <class BidiIterator, class Allocator, class traits>

   286 inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)

   287 {

   288    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);

   289    --pmp;

   290    if(pmp < m_stack_base)

   291    {

   292       extend_stack();

   293       pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);

   294       --pmp;

   295    }

   296    (void) new (pmp)saved_repeater<BidiIterator>(i, s, position);

   297    m_backup_state = pmp;

   298 }

   299 

   300 template <class BidiIterator, class Allocator, class traits>

   301 inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)

   302 {

   303    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);

   304    --pmp;

   305    if(pmp < m_stack_base)

   306    {

   307       extend_stack();

   308       pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);

   309       --pmp;

   310    }

   311    (void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);

   312    m_backup_state = pmp;

   313 }

   314 

   315 template <class BidiIterator, class Allocator, class traits>

   316 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()

   317 {

   318    int index = static_cast<const re_brace*>(pstate)->index;

   319    switch(index)

   320    {

   321    case 0:

   322       pstate = pstate->next.p;

   323       break;

   324    case -1:

   325    case -2:

   326       {

   327          // forward lookahead assert:

   328          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;

   329          pstate = pstate->next.p->next.p;

   330          push_assertion(next_pstate, index == -1);

   331          break;

   332       }

   333    case -3:

   334       {

   335          // independent sub-expression, currently this is always recursive:

   336          bool old_independent = m_independent;

   337          m_independent = true;

   338          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;

   339          pstate = pstate->next.p->next.p;

   340          bool r = match_all_states();

   341          pstate = next_pstate;

   342          m_independent = old_independent;

   343 #ifdef BOOST_REGEX_MATCH_EXTRA

   344          if(r && (m_match_flags & match_extra))

   345          {

   346             //

   347             // our captures have been stored in *m_presult

   348             // we need to unpack them, and insert them

   349             // back in the right order when we unwind the stack:

   350             //

   351             match_results<BidiIterator, Allocator> temp_match(*m_presult);

   352             unsigned i;

   353             for(i = 0; i < temp_match.size(); ++i)

   354                (*m_presult)[i].get_captures().clear();

   355             // match everything else:

   356             r = match_all_states();

   357             // now place the stored captures back:

   358             for(i = 0; i < temp_match.size(); ++i)

   359             {

   360                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;

   361                seq& s1 = (*m_presult)[i].get_captures();

   362                const seq& s2 = temp_match[i].captures();

   363                s1.insert(

   364                   s1.end(), 

   365                   s2.begin(), 

   366                   s2.end());

   367             }

   368          }

   369 #endif

   370          return r;

   371       }

   372    case -4:

   373       {

   374       // conditional expression:

   375       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);

   376       BOOST_ASSERT(alt->type == syntax_element_alt);

   377       pstate = alt->next.p;

   378       if(pstate->type == syntax_element_assert_backref)

   379       {

   380          if(!match_assert_backref())

   381             pstate = alt->alt.p;

   382          break;

   383       }

   384       else

   385       {

   386          // zero width assertion, have to match this recursively:

   387          BOOST_ASSERT(pstate->type == syntax_element_startmark);

   388          bool negated = static_cast<const re_brace*>(pstate)->index == -2;

   389          BidiIterator saved_position = position;

   390          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;

   391          pstate = pstate->next.p->next.p;

   392          bool r = match_all_states();

   393          position = saved_position;

   394          if(negated)

   395             r = !r;

   396          if(r)

   397             pstate = next_pstate;

   398          else

   399             pstate = alt->alt.p;

   400          break;

   401       }

   402       }

   403    default:

   404    {

   405       BOOST_ASSERT(index > 0);

   406       if((m_match_flags & match_nosubs) == 0)

   407       {

   408          push_matched_paren(index, (*m_presult)[index]);

   409          m_presult->set_first(position, index);

   410       }

   411       pstate = pstate->next.p;

   412       break;

   413    }

   414    }

   415    return true;

   416 }

   417 

   418 template <class BidiIterator, class Allocator, class traits>

   419 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()

   420 {

   421    bool take_first, take_second;

   422    const re_alt* jmp = static_cast<const re_alt*>(pstate);

   423 

   424    // find out which of these two alternatives we need to take:

   425    if(position == last)

   426    {

   427       take_first = jmp->can_be_null & mask_take;

   428       take_second = jmp->can_be_null & mask_skip;

   429    }

   430    else

   431    {

   432       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);

   433       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);

   434   }

   435 

   436    if(take_first)

   437    {

   438       // we can take the first alternative,

   439       // see if we need to push next alternative:

   440       if(take_second)

   441       {

   442          push_alt(jmp->alt.p);

   443       }

   444       pstate = pstate->next.p;

   445       return true;

   446    }

   447    if(take_second)

   448    {

   449       pstate = jmp->alt.p;

   450       return true;

   451    }

   452    return false;  // neither option is possible

   453 }

   454 

   455 template <class BidiIterator, class Allocator, class traits>

   456 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()

   457 {

   458 #ifdef BOOST_MSVC

   459 #pragma warning(push)

   460 #pragma warning(disable:4127 4244)

   461 #endif

   462 #ifdef __BORLANDC__

   463 #pragma option push -w-8008 -w-8066 -w-8004

   464 #endif

   465    const re_repeat* rep = static_cast<const re_repeat*>(pstate);

   466 

   467    // find out which of these two alternatives we need to take:

   468    bool take_first, take_second;

   469    if(position == last)

   470    {

   471       take_first = rep->can_be_null & mask_take;

   472       take_second = rep->can_be_null & mask_skip;

   473    }

   474    else

   475    {

   476       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);

   477       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);

   478    }

   479 

   480    if((m_backup_state->state_id != saved_state_repeater_count) 

   481       || (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)

   482       || (next_count->get_id() != rep->state_id))

   483    {

   484       // we're moving to a different repeat from the last

   485       // one, so set up a counter object:

   486       push_repeater_count(rep->state_id, &next_count);

   487    }

   488    //

   489    // If we've had at least one repeat already, and the last one 

   490    // matched the NULL string then set the repeat count to

   491    // maximum:

   492    //

   493    next_count->check_null_repeat(position, rep->max);

   494 

   495    if(next_count->get_count() < rep->min)

   496    {

   497       // we must take the repeat:

   498       if(take_first)

   499       {

   500          // increase the counter:

   501          ++(*next_count);

   502          pstate = rep->next.p;

   503          return true;

   504       }

   505       return false;

   506    }

   507 

   508    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);   

   509    if(greedy)

   510    {

   511       // try and take the repeat if we can:

   512       if((next_count->get_count() < rep->max) && take_first)

   513       {

   514          if(take_second)

   515          {

   516             // store position in case we fail:

   517             push_alt(rep->alt.p);

   518          }

   519          // increase the counter:

   520          ++(*next_count);

   521          pstate = rep->next.p;

   522          return true;

   523       }

   524       else if(take_second)

   525       {

   526          pstate = rep->alt.p;

   527          return true;

   528       }

   529       return false; // can't take anything, fail...

   530    }

   531    else // non-greedy

   532    {

   533       // try and skip the repeat if we can:

   534       if(take_second)

   535       {

   536          if((next_count->get_count() < rep->max) && take_first)

   537          {

   538             // store position in case we fail:

   539             push_non_greedy_repeat(rep->next.p);

   540          }

   541          pstate = rep->alt.p;

   542          return true;

   543       }

   544       if((next_count->get_count() < rep->max) && take_first)

   545       {

   546          // increase the counter:

   547          ++(*next_count);

   548          pstate = rep->next.p;

   549          return true;

   550       }

   551    }

   552    return false;

   553 #ifdef __BORLANDC__

   554 #pragma option pop

   555 #endif

   556 #ifdef BOOST_MSVC

   557 #pragma warning(pop)

   558 #endif

   559 }

   560 

   561 template <class BidiIterator, class Allocator, class traits>

   562 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()

   563 {

   564    unsigned count = 0;

   565    const re_repeat* rep = static_cast<const re_repeat*>(pstate);

   566    re_syntax_base* psingle = rep->next.p;

   567    // match compulsary repeats first:

   568    while(count < rep->min)

   569    {

   570       pstate = psingle;

   571       if(!match_wild())

   572          return false;

   573       ++count;

   574    }

   575    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);   

   576    if(greedy)

   577    {

   578       // repeat for as long as we can:

   579       while(count < rep->max)

   580       {

   581          pstate = psingle;

   582          if(!match_wild())

   583             break;

   584          ++count;

   585       }

   586       // remember where we got to if this is a leading repeat:

   587       if((rep->leading) && (count < rep->max))

   588          restart = position;

   589       // push backtrack info if available:

   590       if(count - rep->min)

   591          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);

   592       // jump to next state:

   593       pstate = rep->alt.p;

   594       return true;

   595    }

   596    else

   597    {

   598       // non-greedy, push state and return true if we can skip:

   599       if(count < rep->max)

   600          push_single_repeat(count, rep, position, saved_state_rep_slow_dot);

   601       pstate = rep->alt.p;

   602       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);

   603    }

   604 }

   605 

   606 template <class BidiIterator, class Allocator, class traits>

   607 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()

   608 {

   609    if(m_match_flags & match_not_dot_null)

   610       return match_dot_repeat_slow();

   611    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)

   612       return match_dot_repeat_slow();

   613 

   614    const re_repeat* rep = static_cast<const re_repeat*>(pstate);

   615    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);   

   616    unsigned count = static_cast<unsigned>((std::min)(static_cast<unsigned>(::boost::re_detail::distance(position, last)), static_cast<unsigned>(greedy ? rep->max : rep->min)));

   617    if(rep->min > count)

   618    {

   619       position = last;

   620       return false;  // not enough text left to match

   621    }

   622    std::advance(position, count);

   623 

   624    if(greedy)

   625    {

   626       if((rep->leading) && (count < rep->max))

   627          restart = position;

   628       // push backtrack info if available:

   629       if(count - rep->min)

   630          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);

   631       // jump to next state:

   632       pstate = rep->alt.p;

   633       return true;

   634    }

   635    else

   636    {

   637       // non-greedy, push state and return true if we can skip:

   638       if(count < rep->max)

   639          push_single_repeat(count, rep, position, saved_state_rep_fast_dot);

   640       pstate = rep->alt.p;

   641       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);

   642    }

   643 }

   644 

   645 template <class BidiIterator, class Allocator, class traits>

   646 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()

   647 {

   648 #ifdef BOOST_MSVC

   649 #pragma warning(push)

   650 #pragma warning(disable:4127)

   651 #endif

   652 #ifdef __BORLANDC__

   653 #pragma option push -w-8008 -w-8066 -w-8004

   654 #endif

   655    const re_repeat* rep = static_cast<const re_repeat*>(pstate);

   656    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);

   657    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);

   658    std::size_t count = 0;

   659    //

   660    // start by working out how much we can skip:

   661    //

   662    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);   

   663    std::size_t desired = greedy ? rep->max : rep->min;

   664    if(::boost::is_random_access_iterator<BidiIterator>::value)

   665    {

   666       BidiIterator end = position;

   667       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));

   668       BidiIterator origin(position);

   669       while((position != end) && (traits_inst.translate(*position, icase) == what))

   670       {

   671          ++position;

   672       }

   673       count = (unsigned)::boost::re_detail::distance(origin, position);

   674    }

   675    else

   676    {

   677       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))

   678       {

   679          ++position;

   680          ++count;

   681       }

   682    }

   683 

   684    if(count < rep->min)

   685       return false;

   686 

   687    if(greedy)

   688    {

   689       if((rep->leading) && (count < rep->max))

   690          restart = position;

   691       // push backtrack info if available:

   692       if(count - rep->min)

   693          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);

   694       // jump to next state:

   695       pstate = rep->alt.p;

   696       return true;

   697    }

   698    else

   699    {

   700       // non-greedy, push state and return true if we can skip:

   701       if(count < rep->max)

   702          push_single_repeat(count, rep, position, saved_state_rep_char);

   703       pstate = rep->alt.p;

   704       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);

   705    }

   706 #ifdef __BORLANDC__

   707 #pragma option pop

   708 #endif

   709 #ifdef BOOST_MSVC

   710 #pragma warning(pop)

   711 #endif

   712 }

   713 

   714 template <class BidiIterator, class Allocator, class traits>

   715 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()

   716 {

   717 #ifdef BOOST_MSVC

   718 #pragma warning(push)

   719 #pragma warning(disable:4127)

   720 #endif

   721 #ifdef __BORLANDC__

   722 #pragma option push -w-8008 -w-8066 -w-8004

   723 #endif

   724    const re_repeat* rep = static_cast<const re_repeat*>(pstate);

   725    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;

   726    std::size_t count = 0;

   727    //

   728    // start by working out how much we can skip:

   729    //

   730    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);   

   731    std::size_t desired = greedy ? rep->max : rep->min;

   732    if(::boost::is_random_access_iterator<BidiIterator>::value)

   733    {

   734       BidiIterator end = position;

   735       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));

   736       BidiIterator origin(position);

   737       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])

   738       {

   739          ++position;

   740       }

   741       count = (unsigned)::boost::re_detail::distance(origin, position);

   742    }

   743    else

   744    {

   745       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])

   746       {

   747          ++position;

   748          ++count;

   749       }

   750    }

   751 

   752    if(count < rep->min)

   753       return false;

   754 

   755    if(greedy)

   756    {

   757       if((rep->leading) && (count < rep->max))

   758          restart = position;

   759       // push backtrack info if available:

   760       if(count - rep->min)

   761          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);

   762       // jump to next state:

   763       pstate = rep->alt.p;

   764       return true;

   765    }

   766    else

   767    {

   768       // non-greedy, push state and return true if we can skip:

   769       if(count < rep->max)

   770          push_single_repeat(count, rep, position, saved_state_rep_short_set);

   771       pstate = rep->alt.p;

   772       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);

   773    }

   774 #ifdef __BORLANDC__

   775 #pragma option pop

   776 #endif

   777 #ifdef BOOST_MSVC

   778 #pragma warning(pop)

   779 #endif

   780 }

   781 

   782 template <class BidiIterator, class Allocator, class traits>

   783 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()

   784 {

   785 #ifdef BOOST_MSVC

   786 #pragma warning(push)

   787 #pragma warning(disable:4127)

   788 #endif

   789 #ifdef __BORLANDC__

   790 #pragma option push -w-8008 -w-8066 -w-8004

   791 #endif

   792    typedef typename traits::char_class_type mask_type;

   793    const re_repeat* rep = static_cast<const re_repeat*>(pstate);

   794    const re_set_long<mask_type>* set = static_cast<const re_set_long<mask_type>*>(pstate->next.p);

   795    std::size_t count = 0;

   796    //

   797    // start by working out how much we can skip:

   798    //

   799    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);   

   800    std::size_t desired = greedy ? rep->max : rep->min;

   801    if(::boost::is_random_access_iterator<BidiIterator>::value)

   802    {

   803       BidiIterator end = position;

   804       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));

   805       BidiIterator origin(position);

   806       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))

   807       {

   808          ++position;

   809       }

   810       count = (unsigned)::boost::re_detail::distance(origin, position);

   811    }

   812    else

   813    {

   814       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))

   815       {

   816          ++position;

   817          ++count;

   818       }

   819    }

   820 

   821    if(count < rep->min)

   822       return false;

   823 

   824    if(greedy)

   825    {

   826       if((rep->leading) && (count < rep->max))

   827          restart = position;

   828       // push backtrack info if available:

   829       if(count - rep->min)

   830          push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);

   831       // jump to next state:

   832       pstate = rep->alt.p;

   833       return true;

   834    }

   835    else

   836    {

   837       // non-greedy, push state and return true if we can skip:

   838       if(count < rep->max)

   839          push_single_repeat(count, rep, position, saved_state_rep_long_set);

   840       pstate = rep->alt.p;

   841       return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);

   842    }

   843 #ifdef __BORLANDC__

   844 #pragma option pop

   845 #endif

   846 #ifdef BOOST_MSVC

   847 #pragma warning(pop)

   848 #endif

   849 }

   850 

   851 /****************************************************************************

   852 

   853 Unwind and associated proceedures follow, these perform what normal stack

   854 unwinding does in the recursive implementation.

   855 

   856 ****************************************************************************/

   857 

   858 template <class BidiIterator, class Allocator, class traits>

   859 bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)

   860 {

   861    static unwind_proc_type const s_unwind_table[14] = 

   862    {

   863       &perl_matcher<BidiIterator, Allocator, traits>::unwind_end,

   864       &perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,

   865       &perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,

   866       &perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,

   867       &perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,

   868       &perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,

   869       &perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,

   870       &perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,

   871       &perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,

   872       &perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,

   873       &perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,

   874       &perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,

   875       &perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,

   876       &perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,

   877    };

   878 

   879    m_recursive_result = have_match;

   880    unwind_proc_type unwinder;

   881    bool cont;

   882    //

   883    // keep unwinding our stack until we have something to do:

   884    //

   885    do

   886    {

   887       unwinder = s_unwind_table[m_backup_state->state_id];

   888       cont = (this->*unwinder)(m_recursive_result);

   889    }while(cont);

   890    //

   891    // return true if we have more states to try:

   892    //

   893    return pstate ? true : false;

   894 }

   895 

   896 template <class BidiIterator, class Allocator, class traits>

   897 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)

   898 {

   899    pstate = 0;   // nothing left to search

   900    return false; // end of stack nothing more to search

   901 }

   902 

   903 template <class BidiIterator, class Allocator, class traits>

   904 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)

   905 {

   906    saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);

   907    // restore previous values if no match was found:

   908    if(have_match == false)

   909    {

   910       m_presult->set_first(pmp->sub.first, pmp->index);

   911       m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched);

   912    }

   913 #ifdef BOOST_REGEX_MATCH_EXTRA

   914    //

   915    // we have a match, push the capture information onto the stack:

   916    //

   917    else if(pmp->sub.matched && (match_extra & m_match_flags))

   918       ((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);

   919 #endif

   920    // unwind stack:

   921    m_backup_state = pmp+1;

   922    boost::re_detail::inplace_destroy(pmp);

   923    return true; // keep looking

   924 }

   925 

   926 template <class BidiIterator, class Allocator, class traits>

   927 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)

   928 {

   929    boost::re_detail::inplace_destroy(m_backup_state++);

   930    pstate = 0;   // nothing left to search

   931    return false; // end of stack nothing more to search

   932 }

   933 

   934 template <class BidiIterator, class Allocator, class traits>

   935 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)

   936 {

   937    saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);

   938    pstate = pmp->pstate;

   939    position = pmp->position;

   940    bool result = (r == pmp->positive);

   941    m_recursive_result = pmp->positive ? r : !r;

   942    boost::re_detail::inplace_destroy(pmp++);

   943    m_backup_state = pmp;

   944    return !result; // return false if the assertion was matched to stop search.

   945 }

   946 

   947 template <class BidiIterator, class Allocator, class traits>

   948 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)

   949 {

   950    saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);

   951    if(!r)

   952    {

   953       pstate = pmp->pstate;

   954       position = pmp->position;

   955    }

   956    boost::re_detail::inplace_destroy(pmp++);

   957    m_backup_state = pmp;

   958    return r; 

   959 }

   960 

   961 template <class BidiIterator, class Allocator, class traits>

   962 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)

   963 {

   964    saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);

   965    boost::re_detail::inplace_destroy(pmp++);

   966    m_backup_state = pmp;

   967    return true; // keep looking

   968 }

   969 

   970 template <class BidiIterator, class Allocator, class traits>

   971 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)

   972 {

   973    saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);

   974    void* condemmed = m_stack_base;

   975    m_stack_base = pmp->base;

   976    m_backup_state = pmp->end;

   977    boost::re_detail::inplace_destroy(pmp);

   978    put_mem_block(condemmed);

   979    return true; // keep looking

   980 }

   981 

   982 template <class BidiIterator, class Allocator, class traits>

   983 inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()

   984 {

   985    saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);

   986    boost::re_detail::inplace_destroy(p++);

   987    m_backup_state = p;

   988 }

   989 

   990 template <class BidiIterator, class Allocator, class traits>

   991 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)

   992 {

   993    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);

   994 

   995    // if we have a match, just discard this state:

   996    if(r) 

   997    {

   998       destroy_single_repeat();

   999       return true;

  1000    }

  1001 

  1002    const re_repeat* rep = pmp->rep;

  1003    std::size_t count = pmp->count;

  1004    BOOST_ASSERT(rep->next.p != 0);

  1005    BOOST_ASSERT(rep->alt.p != 0);

  1006 

  1007    count -= rep->min;

  1008    

  1009    if((m_match_flags & match_partial) && (position == last))

  1010       m_has_partial_match = true;

  1011 

  1012    BOOST_ASSERT(count);

  1013    position = pmp->last_position;

  1014 

  1015    // backtrack till we can skip out:

  1016    do

  1017    {

  1018       --position;

  1019       --count;

  1020       ++state_count;

  1021    }while(count && !can_start(*position, rep->_map, mask_skip));

  1022 

  1023    // if we've hit base, destroy this state:

  1024    if(count == 0)

  1025    {

  1026          destroy_single_repeat();

  1027          if(!can_start(*position, rep->_map, mask_skip))

  1028             return true;

  1029    }

  1030    else

  1031    {

  1032       pmp->count = count + rep->min;

  1033       pmp->last_position = position;

  1034    }

  1035    pstate = rep->alt.p;

  1036    return false;

  1037 }

  1038 

  1039 template <class BidiIterator, class Allocator, class traits>

  1040 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)

  1041 {

  1042    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);

  1043 

  1044    // if we have a match, just discard this state:

  1045    if(r) 

  1046    {

  1047       destroy_single_repeat();

  1048       return true;

  1049    }

  1050 

  1051    const re_repeat* rep = pmp->rep;

  1052    std::size_t count = pmp->count;

  1053    BOOST_ASSERT(rep->type == syntax_element_dot_rep);

  1054    BOOST_ASSERT(rep->next.p != 0);

  1055    BOOST_ASSERT(rep->alt.p != 0);

  1056    BOOST_ASSERT(rep->next.p->type == syntax_element_wild);

  1057 

  1058    BOOST_ASSERT(count < rep->max);

  1059    pstate = rep->next.p;

  1060    position = pmp->last_position;

  1061 

  1062    if(position != last)

  1063    {

  1064       // wind forward until we can skip out of the repeat:

  1065       do

  1066       {

  1067          if(!match_wild())

  1068          {

  1069             // failed repeat match, discard this state and look for another:

  1070             destroy_single_repeat();

  1071             return true;

  1072          }

  1073          ++count;

  1074          ++state_count;

  1075          pstate = rep->next.p;

  1076       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));

  1077    }   

  1078    if(position == last)

  1079    {

  1080       // can't repeat any more, remove the pushed state: 

  1081       destroy_single_repeat();

  1082       if((m_match_flags & match_partial) && (position == last) && (position != search_base))

  1083          m_has_partial_match = true;

  1084       if(0 == (rep->can_be_null & mask_skip))

  1085          return true;

  1086    }

  1087    else if(count == rep->max)

  1088    {

  1089       // can't repeat any more, remove the pushed state: 

  1090       destroy_single_repeat();

  1091       if(!can_start(*position, rep->_map, mask_skip))

  1092          return true;

  1093    }

  1094    else

  1095    {

  1096       pmp->count = count;

  1097       pmp->last_position = position;

  1098    }

  1099    pstate = rep->alt.p;

  1100    return false;

  1101 }

  1102 

  1103 template <class BidiIterator, class Allocator, class traits>

  1104 bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)

  1105 {

  1106    saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);

  1107 

  1108    // if we have a match, just discard this state:

  1109    if(r) 

  1110    {

  1111       destroy_single_repeat();

  1112       return true;

  1113    }

  1114 

  1115    const re_repeat* rep = pmp->rep;

  1116    std::size_t count = pmp->count;

  1117 

  1118    BOOST_ASSERT(count < rep->max);

  1119    position = pmp->last_position;

  1120    if(position != last)

  1121    {

  1122 

  1123       // wind forward until we can skip out of the repeat:

  1124       do

  1125       {

  1126          ++position;

  1127          ++count;

  1128          ++state_count;

  1129       }while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));

  1130    }

  1131 

  1132    if(position == last)

  1133    {

  1134       // can't repeat any more, remove the pushed state: 

  1135       destroy_single_repeat();