/*

 *

 * 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 

  *                common to both the recursive and non-recursive versions.

  */

#ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP

#define BOOST_REGEX_V4_PERL_MATCHER_COMMON_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 __BORLANDC__

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

#endif

#ifdef BOOST_MSVC

#  pragma warning(push)

#  pragma warning(disable: 4800)

#endif

namespace boost{

namespace re_detail{

template <class BidiIterator, class Allocator, class traits>

void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)

{ 

   typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;

   typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;

   if(e.empty())

   {

      // precondition failure: e is not a valid regex.

      std::invalid_argument ex("Invalid regular expression object");

      boost::throw_exception(ex);

   }

   pstate = 0;

   m_match_flags = f;

   estimate_max_state_count(static_cast<category*>(0));

   expression_flag_type re_f = re.flags();

   icase = re_f & regex_constants::icase;

   if(!(m_match_flags & (match_perl|match_posix)))

   {

      if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)

         m_match_flags |= match_perl;

      else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))

         m_match_flags |= match_perl;

      else

         m_match_flags |= match_posix;

   }

   if(m_match_flags & match_posix)

   {

      m_temp_match.reset(new match_results<BidiIterator, Allocator>());

      m_presult = m_temp_match.get();

   }

   else

      m_presult = &m_result;

#ifdef BOOST_REGEX_NON_RECURSIVE

   m_stack_base = 0;

   m_backup_state = 0;

#endif

   // find the value to use for matching word boundaries:

   m_word_mask = re.get_data().m_word_mask; 

   // find bitmask to use for matching '.':

   match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? re_detail::test_not_newline : re_detail::test_newline);

}

template <class BidiIterator, class Allocator, class traits>

void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)

{

   //

   // How many states should we allow our machine to visit before giving up?

   // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)

   // where N is the length of the string, and S is the number of states

   // in the machine.  It's tempting to up this to O(N^2S) or even O(N^2S^2)

   // but these take unreasonably amounts of time to bale out in pathological

   // cases.

   //

   // Calculate NS^2 first:

   //

   static const boost::uintmax_t k = 100000;

   boost::uintmax_t dist = boost::re_detail::distance(base, last);

   if(dist == 0)

      dist = 1;

   boost::uintmax_t states = re.size();

   if(states == 0)

      states = 1;

   states *= states;

   if((std::numeric_limits<boost::uintmax_t>::max)() / dist < states)

   {

      max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;

      return;

   }

   states *= dist;

   if((std::numeric_limits<boost::uintmax_t>::max)() - k < states)

   {

      max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;

      return;

   }

   states += k;

   max_state_count = states;

   //

   // Now calculate N^2:

   //

   states = dist;

   if((std::numeric_limits<boost::uintmax_t>::max)() / dist < states)

   {

      max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;

      return;

   }

   states *= dist;

   if((std::numeric_limits<boost::uintmax_t>::max)() - k < states)

   {

      max_state_count = (std::numeric_limits<boost::uintmax_t>::max)() - 2;

      return;

   }

   states += k;

   //

   // N^2 can be a very large number indeed, to prevent things getting out

   // of control, cap the max states:

   //

   if(states > BOOST_REGEX_MAX_STATE_COUNT)

      states = BOOST_REGEX_MAX_STATE_COUNT;

   //

   // If (the possibly capped) N^2 is larger than our first estimate,

   // use this instead:

   //

   if(states > max_state_count)

      max_state_count = states;

}

template <class BidiIterator, class Allocator, class traits>

inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)

{

   // we don't know how long the sequence is:

   max_state_count = BOOST_REGEX_MAX_STATE_COUNT;

}

#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD

template <class BidiIterator, class Allocator, class traits>

inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(

   protected_proc_type proc)

{

   ::boost::re_detail::concrete_protected_call

      <perl_matcher<BidiIterator, Allocator, traits> >

      obj(this, proc);

   return obj.execute();

}

#endif

template <class BidiIterator, class Allocator, class traits>

inline bool perl_matcher<BidiIterator, Allocator, traits>::match()

{

#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD

   return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);

#else

   return match_imp();

#endif

}

template <class BidiIterator, class Allocator, class traits>

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

{

   // initialise our stack if we are non-recursive:

#ifdef BOOST_REGEX_NON_RECURSIVE

   save_state_init init(&m_stack_base, &m_backup_state);

   used_block_count = BOOST_REGEX_MAX_BLOCKS;

#if !defined(BOOST_NO_EXCEPTIONS)

   try{

#endif

#endif

   // reset our state machine:

   position = base;

   search_base = base;

   state_count = 0;

   m_match_flags |= regex_constants::match_all;

   m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);

   m_presult->set_base(base);

   if(m_match_flags & match_posix)

      m_result = *m_presult;

   verify_options(re.flags(), m_match_flags);

   if(0 == match_prefix())

      return false;

   return m_result[0].second == last;

#if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)

   }

   catch(...)

   {

      // unwind all pushed states, apart from anything else this

      // ensures that all the states are correctly destructed

      // not just the memory freed.

      while(unwind(true)){}

      throw;

   }

#endif

}

template <class BidiIterator, class Allocator, class traits>

inline bool perl_matcher<BidiIterator, Allocator, traits>::find()

{

#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD

   return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);

#else

   return find_imp();

#endif

}

template <class BidiIterator, class Allocator, class traits>

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

{

   static matcher_proc_type const s_find_vtable[7] = 

   {

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

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

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

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

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

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

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

   };

   // initialise our stack if we are non-recursive:

#ifdef BOOST_REGEX_NON_RECURSIVE

   save_state_init init(&m_stack_base, &m_backup_state);

   used_block_count = BOOST_REGEX_MAX_BLOCKS;

#if !defined(BOOST_NO_EXCEPTIONS)

   try{

#endif

#endif

   state_count = 0;

   if((m_match_flags & regex_constants::match_init) == 0)

   {

      // reset our state machine:

      search_base = position = base;

      pstate = re.get_first_state();

      m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), base, last);

      m_presult->set_base(base);

      m_match_flags |= regex_constants::match_init;

   }

   else

   {

      // start again:

      search_base = position = m_result[0].second;

      // If last match was null and match_not_null was not set then increment

      // our start position, otherwise we go into an infinite loop:

      if(((m_match_flags & match_not_null) == 0) && (m_result.length() == 0))

      {

         if(position == last)

            return false;

         else 

            ++position;

      }

      // reset $` start:

      m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);

      //if((base != search_base) && (base == backstop))

      //   m_match_flags |= match_prev_avail;

   }

   if(m_match_flags & match_posix)

   {

      m_result.set_size(re.mark_count(), base, last);

      m_result.set_base(base);

   }

   verify_options(re.flags(), m_match_flags);

   // find out what kind of expression we have:

   unsigned type = (m_match_flags & match_continuous) ? 

      static_cast<unsigned int>(regbase::restart_continue) 

         : static_cast<unsigned int>(re.get_restart_type());

   // call the appropriate search routine:

   matcher_proc_type proc = s_find_vtable[type];

   return (this->*proc)();

#if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)

   }

   catch(...)

   {

      // unwind all pushed states, apart from anything else this

      // ensures that all the states are correctly destructed

      // not just the memory freed.

      while(unwind(true)){}

      throw;

   }

#endif

}

template <class BidiIterator, class Allocator, class traits>

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

{

   m_has_partial_match = false;

   m_has_found_match = false;

   pstate = re.get_first_state();

   m_presult->set_first(position);

   restart = position;

   match_all_states();

   if(!m_has_found_match && m_has_partial_match && (m_match_flags & match_partial))

   {

      m_has_found_match = true;

      m_presult->set_second(last, 0, false);

      position = last;

   }

#ifdef BOOST_REGEX_MATCH_EXTRA

   if(m_has_found_match && (match_extra & m_match_flags))

   {

      //

      // we have a match, reverse the capture information:

      //

      for(unsigned i = 0; i < m_presult->size(); ++i)

      {

         typename sub_match<BidiIterator>::capture_sequence_type & seq = ((*m_presult)[i]).get_captures();

         std::reverse(seq.begin(), seq.end());

      }

   }

#endif

   if(!m_has_found_match)

      position = restart; // reset search postion

   return m_has_found_match;

}

template <class BidiIterator, class Allocator, class traits>

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

{

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

   if(index > 0)

   {

      if((m_match_flags & match_nosubs) == 0)

         m_presult->set_second(position, index);

   }

   else if((index < 0) && (index != -4))

   {

      // matched forward lookahead:

      pstate = 0;

      return true;

   }

   pstate = pstate->next.p;

   return true;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   unsigned int len = static_cast<const re_literal*>(pstate)->length;

   const char_type* what = reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);

   //

   // compare string with what we stored in

   // our records:

   for(unsigned int i = 0; i < len; ++i, ++position)

   {

      if((position == last) || (traits_inst.translate(*position, icase) != what[i]))

         return false;

   }

   pstate = pstate->next.p;

   return true;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   if(position == backstop)

   {

      if((m_match_flags & match_prev_avail) == 0)

      {

         if((m_match_flags & match_not_bol) == 0)

         {

            pstate = pstate->next.p;

            return true;

         }

         return false;

      }

   }

   else if(m_match_flags & match_single_line)

      return false;

   // check the previous value character:

   BidiIterator t(position);

   --t;

   if(position != last)

   {

      if(is_separator(*t) && !((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n'))) )

      {

         pstate = pstate->next.p;

         return true;

      }

   }

   else if(is_separator(*t))

   {

      pstate = pstate->next.p;

      return true;

   }

   return false;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   if(position != last)

   {

      if(m_match_flags & match_single_line)

         return false;

      // we're not yet at the end so *first is always valid:

      if(is_separator(*position))

      {

         if((position != backstop) || (m_match_flags & match_prev_avail))

         {

            // check that we're not in the middle of \r\n sequence

            BidiIterator t(position);

            --t;

            if((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n')))

            {

               return false;

            }

         }

         pstate = pstate->next.p;

         return true;

      }

   }

   else if((m_match_flags & match_not_eol) == 0)

   {

      pstate = pstate->next.p;

      return true;

   }

   return false;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   if(position == last) 

      return false;

   if(is_separator(*position) && ((match_any_mask & static_cast<const re_dot*>(pstate)->mask) == 0))

      return false;

   if((*position == char_type(0)) && (m_match_flags & match_not_dot_null))

      return false;

   pstate = pstate->next.p;

   ++position;

   return true;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))

      return false;

   if((m_match_flags & match_all) && (position != last))

      return false;

   if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))

      return false;

   m_presult->set_second(position);

   pstate = 0;

   m_has_found_match = true;

   if((m_match_flags & match_posix) == match_posix)

   {

      m_result.maybe_assign(*m_presult);

      if((m_match_flags & match_any) == 0)

         return false;

   }

#ifdef BOOST_REGEX_MATCH_EXTRA

   if(match_extra & m_match_flags)

   {

      for(unsigned i = 0; i < m_presult->size(); ++i)

         if((*m_presult)[i].matched)

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

   }

#endif

   return true;

}

template <class BidiIterator, class Allocator, class traits>

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

{

   bool b; // indcates whether next character is a word character

   if(position != last)

   {

      // prev and this character must be opposites:

   #if defined(BOOST_REGEX_USE_C_LOCALE) && defined(__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ < 95)

      b = traits::isctype(*position, m_word_mask);

   #else

      b = traits_inst.isctype(*position, m_word_mask);

   #endif

   }

   else

   {

      b = (m_match_flags & match_not_eow) ? true : false;

   }

   if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))

   {

      if(m_match_flags & match_not_bow)

         b ^= true;

      else

         b ^= false;

   }

   else

   {

      --position;

      b ^= traits_inst.isctype(*position, m_word_mask);

      ++position;

   }

   if(b)

   {

      pstate = pstate->next.p;

      return true;

   }

   return false; // no match if we get to here...