/*

 *

 * Copyright (c) 2002

 * John Maddock

 *

 * Use, modification and distribution are subject to the 

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

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

 *

 */

 /*

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

  *   FILE         perl_matcher_common.cpp

  *   VERSION      see <boost/version.hpp>

  *   DESCRIPTION: Definitions of perl_matcher member functions that are 

  *                specific to the recursive implementation.

  */

#ifndef BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP

#define BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable: 4103)

#endif

#ifdef BOOST_HAS_ABI_HEADERS

#  include BOOST_ABI_PREFIX

#endif

#ifdef BOOST_MSVC

#pragma warning(pop)

#endif

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable: 4800)

#endif

namespace boost{

namespace re_detail{

template <class BidiIterator>

class backup_subex

{

   int index;

   sub_match<BidiIterator> sub;

public:

   template <class A>

   backup_subex(const match_results<BidiIterator, A>& w, int i)

      : index(i), sub(w[i], false) {}

   template <class A>

   void restore(match_results<BidiIterator, A>& w)

   {

      w.set_first(sub.first, index);

      w.set_second(sub.second, index, sub.matched);

   }

   const sub_match<BidiIterator>& get() { return sub; }

};

template <class BidiIterator, class Allocator, class traits>

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

{

   static matcher_proc_type const s_match_vtable[29] = 

   {

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      (::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),

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

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

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

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

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

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

   };

   if(state_count > max_state_count)

      raise_error(traits_inst, regex_constants::error_space);

   while(pstate)

   {

      matcher_proc_type proc = s_match_vtable[pstate->type];

      ++state_count;

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

      {

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

            m_has_partial_match = true;

         return 0;

      }

   }

   return true;

}

template <class BidiIterator, class Allocator, class traits>

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

{

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

   bool r = true;

   switch(index)

   {

   case 0:

      pstate = pstate->next.p;

      break;

   case -1:

   case -2:

      {

         // forward lookahead assert:

         BidiIterator old_position(position);

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

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

         r = match_all_states();

         pstate = next_pstate;

         position = old_position;

         if((r && (index != -1)) || (!r && (index != -2)))

            r = false;

         else

            r = true;

         break;

      }

   case -3:

      {

         // independent sub-expression:

         bool old_independent = m_independent;

         m_independent = true;

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

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

         r = match_all_states();

         pstate = next_pstate;

         m_independent = old_independent;

#ifdef BOOST_REGEX_MATCH_EXTRA

         if(r && (m_match_flags & match_extra))

         {

            //

            // our captures have been stored in *m_presult

            // we need to unpack them, and insert them

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

            //

            unsigned i;

            match_results<BidiIterator, Allocator> tm(*m_presult);

            for(i = 0; i < tm.size(); ++i)

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

            // match everything else:

            r = match_all_states();

            // now place the stored captures back:

            for(i = 0; i < tm.size(); ++i)

            {

               typedef typename sub_match<BidiIterator>::capture_sequence_type seq;

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

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

               s1.insert(

                  s1.end(), 

                  s2.begin(), 

                  s2.end());

            }

         }

#endif

         break;

      }

   case -4:

      {

      // conditional expression:

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

      BOOST_ASSERT(alt->type == syntax_element_alt);

      pstate = alt->next.p;

      if(pstate->type == syntax_element_assert_backref)

      {

         if(!match_assert_backref())

            pstate = alt->alt.p;

         break;

      }

      else

      {

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

         BOOST_ASSERT(pstate->type == syntax_element_startmark);

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

         BidiIterator saved_position = position;

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

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

         bool r = match_all_states();

         position = saved_position;

         if(negated)

            r = !r;

         if(r)

            pstate = next_pstate;

         else

            pstate = alt->alt.p;

         break;

      }

      }

   default:

   {

      BOOST_ASSERT(index > 0);

      if((m_match_flags & match_nosubs) == 0)

      {

         backup_subex<BidiIterator> sub(*m_presult, index);

         m_presult->set_first(position, index);

         pstate = pstate->next.p;

         r = match_all_states();

         if(r == false)

            sub.restore(*m_presult);

#ifdef BOOST_REGEX_MATCH_EXTRA

         //

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

         //

         else if(sub.get().matched && (match_extra & m_match_flags))

            ((*m_presult)[index]).get_captures().push_back(sub.get());

#endif

      }

      else

      {

         pstate = pstate->next.p;

      }

      break;

   }

   }

   return r;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   bool take_first, take_second;

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

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

   if(position == last)

   {

      take_first = jmp->can_be_null & mask_take;

      take_second = jmp->can_be_null & mask_skip;

   }

   else

   {

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

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

  }

   if(take_first)

   {

      // we can take the first alternative,

      // see if we need to push next alternative:

      if(take_second)

      {

         BidiIterator oldposition(position);

         const re_syntax_base* old_pstate = jmp->alt.p;

         pstate = pstate->next.p;

         if(!match_all_states())

         {

            pstate = old_pstate;

            position = oldposition;

         }

         return true;

      }

      pstate = pstate->next.p;

      return true;

   }

   if(take_second)

   {

      pstate = jmp->alt.p;

      return true;

   }

   return false;  // neither option is possible

}

template <class BidiIterator, class Allocator, class traits>

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

{

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable:4127 4244)

#endif

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

   //

   // Always copy the repeat count, so that the state is restored

   // when we exit this scope:

   //

   repeater_count<BidiIterator> r(rep->state_id, &next_count, position);

   //

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

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

   // maximum:

   //

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

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

   bool take_first, take_second;

   if(position == last)

   {

      take_first = rep->can_be_null & mask_take;

      take_second = rep->can_be_null & mask_skip;

   }

   else

   {

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

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

   }

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

   {

      // we must take the repeat:

      if(take_first)

      {

         // increase the counter:

         ++(*next_count);

         pstate = rep->next.p;

         return match_all_states();

      }

      return false;

   }

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

   if(greedy)

   {

      // try and take the repeat if we can:

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

      {

         // store position in case we fail:

         BidiIterator pos = position;

         // increase the counter:

         ++(*next_count);

         pstate = rep->next.p;

         if(match_all_states())

            return true;

         // failed repeat, reset posistion and fall through for alternative:

         position = pos;

      }

      if(take_second)

      {

         pstate = rep->alt.p;

         return true;

      }

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

   }

   else // non-greedy

   {

      // try and skip the repeat if we can:

      if(take_second)

      {

         // store position in case we fail:

         BidiIterator pos = position;

         pstate = rep->alt.p;

         if(match_all_states())

            return true;

         // failed alternative, reset posistion and fall through for repeat:

         position = pos;

      }

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

      {

         // increase the counter:

         ++(*next_count);

         pstate = rep->next.p;

         return match_all_states();

      }

   }

   return false;

#ifdef BOOST_MSVC

#pragma warning(pop)

#endif

}

template <class BidiIterator, class Allocator, class traits>

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

{

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable:4127)

#endif

   unsigned count = 0;

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

   re_syntax_base* psingle = rep->next.p;

   // match compulsary repeats first:

   while(count < rep->min)

   {

      pstate = psingle;

      if(!match_wild())

         return false;

      ++count;

   }

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

   if(greedy)

   {

      // normal repeat:

      while(count < rep->max)

      {

         pstate = psingle;

         if(!match_wild())

            break;

         ++count;

      }

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

         restart = position;

      pstate = rep;

      return backtrack_till_match(count - rep->min);

   }

   else

   {

      // non-greedy, keep trying till we get a match:

      BidiIterator save_pos;

      do

      {

         if((rep->leading) && (rep->max == UINT_MAX))

            restart = position;

         pstate = rep->alt.p;

         save_pos = position;

         ++state_count;

         if(match_all_states())

            return true;

         if(count >= rep->max)

            return false;

         ++count;

         pstate = psingle;

         position = save_pos;

         if(!match_wild())

            return false;

      }while(true);

   }

#ifdef BOOST_MSVC

#pragma warning(pop)

#endif

}

template <class BidiIterator, class Allocator, class traits>

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

{

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable:4127)

#endif

   if(m_match_flags & match_not_dot_null)

      return match_dot_repeat_slow();

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

      return match_dot_repeat_slow();

   //

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

   //

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

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable:4267)

#endif

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

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

   if(rep->min > count)

   {

      position = last;

      return false;  // not enough text left to match

   }

   std::advance(position, count);

#ifdef BOOST_MSVC

#pragma warning(pop)

#endif

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

      restart = position;

   if(greedy)

      return backtrack_till_match(count - rep->min);

   // non-greedy, keep trying till we get a match:

   BidiIterator save_pos;

   do

   {

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

      {

         ++position;

         ++count;

      }

      if((rep->leading) && (rep->max == UINT_MAX))

         restart = position;

      pstate = rep->alt.p;

      save_pos = position;

      ++state_count;

      if(match_all_states())

         return true;

      if(count >= rep->max)

         return false;

      if(save_pos == last)

         return false;

      position = ++save_pos;

      ++count;

   }while(true);

#ifdef BOOST_MSVC

#pragma warning(pop)

#endif

}

template <class BidiIterator, class Allocator, class traits>

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

{

#ifdef BOOST_MSVC

#pragma warning(push)

#pragma warning(disable:4127)

#pragma warning(disable:4267)

#endif

#ifdef __BORLANDC__

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

#endif

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

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

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

   //

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

   //

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

   std::size_t count, desired;

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

   {

      desired = 

         (std::min)(

            (std::size_t)(greedy ? rep->max : rep->min),

            (std::size_t)::boost::re_detail::distance(position, last));

      count = desired;

      ++desired;

      if(icase)

      {