basic_regex_creator.hpp

C++的一个好库。。。现在很流行

/*
 *
 * Copyright (c) 2004
 * 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         basic_regex_creator.cpp
  *   VERSION      see <boost/version.hpp>
  *   DESCRIPTION: Declares template class basic_regex_creator which fills in
  *                the data members of a regex_data object.
  */

#ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
#define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP

#ifdef BOOST_HAS_ABI_HEADERS
#  include BOOST_ABI_PREFIX
#endif

namespace boost{

namespace re_detail{

template <class charT>
struct digraph : public std::pair<charT, charT>
{
   digraph() : std::pair<charT, charT>(0, 0){}
   digraph(charT c1) : std::pair<charT, charT>(c1, 0){}
   digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
   {}
#if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
   digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
#endif
   template <class Seq>
   digraph(const Seq& s) : std::pair<charT, charT>()
   {
      BOOST_ASSERT(s.size() <= 2);
      BOOST_ASSERT(s.size());
      this->first = s[0];
      this->second = (s.size() > 1) ? s[1] : 0;
   }
};

template <class charT, class traits>
class basic_char_set
{
public:
   typedef digraph<charT>                   digraph_type;
   typedef typename traits::string_type     string_type;
   typedef typename traits::char_class_type mask_type;

   basic_char_set()
   {
      m_negate = false;
      m_has_digraphs = false;
      m_classes = 0;
      m_negated_classes = 0;
      m_empty = true;
   }

   void add_single(const digraph_type& s)
   {
      m_singles.insert(m_singles.end(), s);
      if(s.second)
         m_has_digraphs = true;
      m_empty = false;
   }
   void add_range(const digraph_type& first, const digraph_type& end)
   {
      m_ranges.insert(m_ranges.end(), first);
      m_ranges.insert(m_ranges.end(), end);
      if(first.second)
      {
         m_has_digraphs = true;
         add_single(first);
      }
      if(end.second)
      {
         m_has_digraphs = true;
         add_single(end);
      }
      m_empty = false;
   }
   void add_class(mask_type m)
   {
      m_classes |= m;
      m_empty = false;
   }
   void add_negated_class(mask_type m)
   {
      m_negated_classes |= m;
      m_empty = false;
   }
   void add_equivalent(const digraph_type& s)
   {
      m_equivalents.insert(m_equivalents.end(), s);
      if(s.second)
      {
         m_has_digraphs = true;
         add_single(s);
      }
      m_empty = false;
   }
   void negate()
   { 
      m_negate = true;
      //m_empty = false;
   }

   //
   // accessor functions:
   //
   bool has_digraphs()const
   {
      return m_has_digraphs;
   }
   bool is_negated()const
   {
      return m_negate;
   }
   typedef typename std::vector<digraph_type>::const_iterator  list_iterator;
   list_iterator singles_begin()const
   {
      return m_singles.begin();
   }
   list_iterator singles_end()const
   {
      return m_singles.end();
   }
   list_iterator ranges_begin()const
   {
      return m_ranges.begin();
   }
   list_iterator ranges_end()const
   {
      return m_ranges.end();
   }
   list_iterator equivalents_begin()const
   {
      return m_equivalents.begin();
   }
   list_iterator equivalents_end()const
   {
      return m_equivalents.end();
   }
   mask_type classes()const
   {
      return m_classes;
   }
   mask_type negated_classes()const
   {
      return m_negated_classes;
   }
   bool empty()const
   {
      return m_empty;
   }
private:
   std::vector<digraph_type> m_singles;         // a list of single characters to match
   std::vector<digraph_type> m_ranges;          // a list of end points of our ranges
   bool                      m_negate;          // true if the set is to be negated
   bool                      m_has_digraphs;    // true if we have digraphs present
   mask_type                 m_classes;         // character classes to match
   mask_type                 m_negated_classes; // negated character classes to match
   bool                      m_empty;           // whether we've added anything yet
   std::vector<digraph_type> m_equivalents;     // a list of equivalence classes
};
   
template <class charT, class traits>
class basic_regex_creator
{
public:
   basic_regex_creator(regex_data<charT, traits>* data);
   std::ptrdiff_t getoffset(void* addr)
   {
      return getoffset(addr, m_pdata->m_data.data());
   }
   std::ptrdiff_t getoffset(const void* addr, const void* base)
   {
      return static_cast<const char*>(addr) - static_cast<const char*>(base);
   }
   re_syntax_base* getaddress(std::ptrdiff_t off)
   {
      return getaddress(off, m_pdata->m_data.data());
   }
   re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
   {
      return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
   }
   void init(unsigned flags)
   {
      m_pdata->m_flags = flags;
      m_icase = flags & regex_constants::icase;
   }
   regbase::flag_type flags()
   {
      return m_pdata->m_flags;
   }
   void flags(regbase::flag_type f)
   {
      m_pdata->m_flags = f;
      if(m_icase != static_cast<bool>(f & regbase::icase))
      {
         m_icase = static_cast<bool>(f & regbase::icase);
      }
   }
   re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
   re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
   re_literal* append_literal(charT c);
   re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
   re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
   re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
   void finalize(const charT* p1, const charT* p2);
protected:
   regex_data<charT, traits>*    m_pdata;              // pointer to the basic_regex_data struct we are filling in
   const ::boost::regex_traits_wrapper<traits>&  
                                 m_traits;             // convenience reference to traits class
   re_syntax_base*               m_last_state;         // the last state we added
   bool                          m_icase;              // true for case insensitive matches
   unsigned                      m_repeater_id;        // the id of the next repeater
   bool                          m_has_backrefs;       // true if there are actually any backrefs
   unsigned                      m_backrefs;           // bitmask of permitted backrefs
   boost::uintmax_t              m_bad_repeats;        // bitmask of repeats we can't deduce a startmap for;
   typename traits::char_class_type m_word_mask;       // mask used to determine if a character is a word character
   typename traits::char_class_type m_mask_space;      // mask used to determine if a character is a word character
   typename traits::char_class_type m_lower_mask;       // mask used to determine if a character is a lowercase character
   typename traits::char_class_type m_upper_mask;      // mask used to determine if a character is an uppercase character
   typename traits::char_class_type m_alpha_mask;      // mask used to determine if a character is an alphabetic character
private:
   basic_regex_creator& operator=(const basic_regex_creator&);
   basic_regex_creator(const basic_regex_creator&);

   void fixup_pointers(re_syntax_base* state);
   void create_startmaps(re_syntax_base* state);
   int calculate_backstep(re_syntax_base* state);
   void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
   unsigned get_restart_type(re_syntax_base* state);
   void set_all_masks(unsigned char* bits, unsigned char);
   bool is_bad_repeat(re_syntax_base* pt);
   void set_bad_repeat(re_syntax_base* pt);
   syntax_element_type get_repeat_type(re_syntax_base* state);
   void probe_leading_repeat(re_syntax_base* state);
};

template <class charT, class traits>
basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
   : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_repeater_id(0), m_has_backrefs(false), m_backrefs(0)
{
   m_pdata->m_data.clear();
   m_pdata->m_status = ::boost::regex_constants::error_ok;
   static const charT w = 'w';
   static const charT s = 's';
   static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
   static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
   static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
   m_word_mask = m_traits.lookup_classname(&w, &w +1);
   m_mask_space = m_traits.lookup_classname(&s, &s +1);
   m_lower_mask = m_traits.lookup_classname(l, l + 5);
   m_upper_mask = m_traits.lookup_classname(u, u + 5);
   m_alpha_mask = m_traits.lookup_classname(a, a + 5);
   BOOST_ASSERT(m_word_mask != 0); 
   BOOST_ASSERT(m_mask_space != 0); 
   BOOST_ASSERT(m_lower_mask != 0); 
   BOOST_ASSERT(m_upper_mask != 0); 
   BOOST_ASSERT(m_alpha_mask != 0); 
}

template <class charT, class traits>
re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
{
   // if the state is a backref then make a note of it:
   if(t == syntax_element_backref)
      this->m_has_backrefs = true;
   // append a new state, start by aligning our last one:
   m_pdata->m_data.align();
   // set the offset to the next state in our last one:
   if(m_last_state)
      m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
   // now actually extent our data:
   m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
   // fill in boilerplate options in the new state:
   m_last_state->next.i = 0;
   m_last_state->type = t;
   return m_last_state;
}

template <class charT, class traits>
re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
{
   // append a new state, start by aligning our last one:
   m_pdata->m_data.align();
   // set the offset to the next state in our last one:
   if(m_last_state)
      m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
   // remember the last state position:
   std::ptrdiff_t off = getoffset(m_last_state) + s;
   // now actually insert our data:
   re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
   // fill in boilerplate options in the new state:
   new_state->next.i = s;
   new_state->type = t;
   m_last_state = getaddress(off);
   return new_state;
}

template <class charT, class traits>
re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
{
   re_literal* result;
   // start by seeing if we have an existing re_literal we can extend:
   if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
   {
      // no existing re_literal, create a new one:
      result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
      result->length = 1;
      *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
   }
   else
   {
      // we have an existing re_literal, extend it:
      std::ptrdiff_t off = getoffset(m_last_state);
      m_pdata->m_data.extend(sizeof(charT));
      m_last_state = result = static_cast<re_literal*>(getaddress(off));
      charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
      characters[result->length] = m_traits.translate(c, m_icase);
      ++(result->length);
   }
   return result;
}

template <class charT, class traits>
inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
   const basic_char_set<charT, traits>& char_set)
{
   typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
   return char_set.has_digraphs() 
      ? append_set(char_set, static_cast<mpl::false_*>(0))
      : append_set(char_set, static_cast<truth_type*>(0));
}

template <class charT, class traits>
re_syntax_base* basic_regex_creator<charT, traits>::append_set(
   const basic_char_set<charT, traits>& char_set, mpl::false_*)
{
   typedef typename traits::string_type string_type;
   typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
   typedef typename traits::char_class_type mask_type;
   
   re_set_long<mask_type>* result = static_cast<re_set_long<mask_type>*>(append_state(syntax_element_long_set, sizeof(re_set_long<mask_type>)));
   //
   // fill in the basics:
   //
   result->csingles = static_cast<unsigned int>(::boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end()));
   result->cranges = static_cast<unsigned int>(::boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
   result->cequivalents = static_cast<unsigned int>(::boost::re_detail::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
   result->cclasses = char_set.classes();
   result->cnclasses = char_set.negated_classes();
   if(flags() & regbase::icase)
   {
      // adjust classes as needed:
      if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
         result->cclasses |= m_alpha_mask;
      if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
         result->cnclasses |= m_alpha_mask;
   }

   result->isnot = char_set.is_negated();
   result->singleton = !char_set.has_digraphs();
   //
   // remember where the state is for later:
   //
   std::ptrdiff_t offset = getoffset(result);
   //
   // now extend with all the singles:
   //
   item_iterator first, last;
   first = char_set.singles_begin();
   last = char_set.singles_end();
   while(first != last)
   {
      charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (first->second ? 3 : 2)));
      p[0] = m_traits.translate(first->first, m_icase);
      if(first->second)
      {
         p[1] = m_traits.translate(first->second, m_icase);
         p[2] = 0;
      }
      else
         p[1] = 0;
      ++first;
   }
   //
   // now extend with all the ranges:
   //
   first = char_set.ranges_begin();
   last = char_set.ranges_end();
   while(first != last)
   {
      // first grab the endpoints of the range:
      digraph<charT> c1 = *first;
      c1.first = this->m_traits.translate(c1.first, this->m_icase);
      c1.second = this->m_traits.translate(c1.second, this->m_icase);
      ++first;
      digraph<charT> c2 = *first;
      c2.first = this->m_traits.translate(c2.first, this->m_icase);
      c2.second = this->m_traits.translate(c2.second, this->m_icase);
      ++first;
      string_type s1, s2;
      // different actions now depending upon whether collation is turned on:
      if(flags() & regex_constants::collate)
      {
         // we need to transform our range into sort keys:
#if BOOST_WORKAROUND(__GNUC__, < 3)
         string_type in(3, charT(0));
         in[0] = c1.first;
         in[1] = c1.second;
         s1 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
         in[0] = c2.first;
         in[1] = c2.second;
         s2 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
#else
         charT a1[3] = { c1.first, c1.second, charT(0), };
         charT a2[3] = { c2.first, c2.second, charT(0), };