Chris@16: /*
Chris@16:  *
Chris@16:  * Copyright (c) 2004
Chris@16:  * John Maddock
Chris@16:  *
Chris@16:  * Use, modification and distribution are subject to the 
Chris@16:  * Boost Software License, Version 1.0. (See accompanying file 
Chris@16:  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  */
Chris@16: 
Chris@16:  /*
Chris@16:   *   LOCATION:    see http://www.boost.org for most recent version.
Chris@16:   *   FILE         basic_regex_creator.cpp
Chris@16:   *   VERSION      see <boost/version.hpp>
Chris@16:   *   DESCRIPTION: Declares template class basic_regex_creator which fills in
Chris@16:   *                the data members of a regex_data object.
Chris@16:   */
Chris@16: 
Chris@16: #ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
Chris@16: #define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
Chris@16: 
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(push)
Chris@16: #pragma warning(disable: 4103)
Chris@16: #endif
Chris@16: #ifdef BOOST_HAS_ABI_HEADERS
Chris@16: #  include BOOST_ABI_PREFIX
Chris@16: #endif
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: #ifdef BOOST_MSVC
Chris@16: #  pragma warning(push)
Chris@16: #  pragma warning(disable: 4800)
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace re_detail{
Chris@16: 
Chris@16: template <class charT>
Chris@16: struct digraph : public std::pair<charT, charT>
Chris@16: {
Chris@16:    digraph() : std::pair<charT, charT>(0, 0){}
Chris@16:    digraph(charT c1) : std::pair<charT, charT>(c1, 0){}
Chris@16:    digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
Chris@16:    {}
Chris@16:    digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
Chris@16:    template <class Seq>
Chris@16:    digraph(const Seq& s) : std::pair<charT, charT>()
Chris@16:    {
Chris@16:       BOOST_ASSERT(s.size() <= 2);
Chris@16:       BOOST_ASSERT(s.size());
Chris@16:       this->first = s[0];
Chris@16:       this->second = (s.size() > 1) ? s[1] : 0;
Chris@16:    }
Chris@16: };
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: class basic_char_set
Chris@16: {
Chris@16: public:
Chris@16:    typedef digraph<charT>                   digraph_type;
Chris@16:    typedef typename traits::string_type     string_type;
Chris@16:    typedef typename traits::char_class_type m_type;
Chris@16: 
Chris@16:    basic_char_set()
Chris@16:    {
Chris@16:       m_negate = false;
Chris@16:       m_has_digraphs = false;
Chris@16:       m_classes = 0;
Chris@16:       m_negated_classes = 0;
Chris@16:       m_empty = true;
Chris@16:    }
Chris@16: 
Chris@16:    void add_single(const digraph_type& s)
Chris@16:    {
Chris@16:       m_singles.insert(m_singles.end(), s);
Chris@16:       if(s.second)
Chris@16:          m_has_digraphs = true;
Chris@16:       m_empty = false;
Chris@16:    }
Chris@16:    void add_range(const digraph_type& first, const digraph_type& end)
Chris@16:    {
Chris@16:       m_ranges.insert(m_ranges.end(), first);
Chris@16:       m_ranges.insert(m_ranges.end(), end);
Chris@16:       if(first.second)
Chris@16:       {
Chris@16:          m_has_digraphs = true;
Chris@16:          add_single(first);
Chris@16:       }
Chris@16:       if(end.second)
Chris@16:       {
Chris@16:          m_has_digraphs = true;
Chris@16:          add_single(end);
Chris@16:       }
Chris@16:       m_empty = false;
Chris@16:    }
Chris@16:    void add_class(m_type m)
Chris@16:    {
Chris@16:       m_classes |= m;
Chris@16:       m_empty = false;
Chris@16:    }
Chris@16:    void add_negated_class(m_type m)
Chris@16:    {
Chris@16:       m_negated_classes |= m;
Chris@16:       m_empty = false;
Chris@16:    }
Chris@16:    void add_equivalent(const digraph_type& s)
Chris@16:    {
Chris@16:       m_equivalents.insert(m_equivalents.end(), s);
Chris@16:       if(s.second)
Chris@16:       {
Chris@16:          m_has_digraphs = true;
Chris@16:          add_single(s);
Chris@16:       }
Chris@16:       m_empty = false;
Chris@16:    }
Chris@16:    void negate()
Chris@16:    { 
Chris@16:       m_negate = true;
Chris@16:       //m_empty = false;
Chris@16:    }
Chris@16: 
Chris@16:    //
Chris@16:    // accessor functions:
Chris@16:    //
Chris@16:    bool has_digraphs()const
Chris@16:    {
Chris@16:       return m_has_digraphs;
Chris@16:    }
Chris@16:    bool is_negated()const
Chris@16:    {
Chris@16:       return m_negate;
Chris@16:    }
Chris@16:    typedef typename std::vector<digraph_type>::const_iterator  list_iterator;
Chris@16:    list_iterator singles_begin()const
Chris@16:    {
Chris@16:       return m_singles.begin();
Chris@16:    }
Chris@16:    list_iterator singles_end()const
Chris@16:    {
Chris@16:       return m_singles.end();
Chris@16:    }
Chris@16:    list_iterator ranges_begin()const
Chris@16:    {
Chris@16:       return m_ranges.begin();
Chris@16:    }
Chris@16:    list_iterator ranges_end()const
Chris@16:    {
Chris@16:       return m_ranges.end();
Chris@16:    }
Chris@16:    list_iterator equivalents_begin()const
Chris@16:    {
Chris@16:       return m_equivalents.begin();
Chris@16:    }
Chris@16:    list_iterator equivalents_end()const
Chris@16:    {
Chris@16:       return m_equivalents.end();
Chris@16:    }
Chris@16:    m_type classes()const
Chris@16:    {
Chris@16:       return m_classes;
Chris@16:    }
Chris@16:    m_type negated_classes()const
Chris@16:    {
Chris@16:       return m_negated_classes;
Chris@16:    }
Chris@16:    bool empty()const
Chris@16:    {
Chris@16:       return m_empty;
Chris@16:    }
Chris@16: private:
Chris@16:    std::vector<digraph_type> m_singles;         // a list of single characters to match
Chris@16:    std::vector<digraph_type> m_ranges;          // a list of end points of our ranges
Chris@16:    bool                      m_negate;          // true if the set is to be negated
Chris@16:    bool                      m_has_digraphs;    // true if we have digraphs present
Chris@16:    m_type                    m_classes;         // character classes to match
Chris@16:    m_type                    m_negated_classes; // negated character classes to match
Chris@16:    bool                      m_empty;           // whether we've added anything yet
Chris@16:    std::vector<digraph_type> m_equivalents;     // a list of equivalence classes
Chris@16: };
Chris@16:    
Chris@16: template <class charT, class traits>
Chris@16: class basic_regex_creator
Chris@16: {
Chris@16: public:
Chris@16:    basic_regex_creator(regex_data<charT, traits>* data);
Chris@16:    std::ptrdiff_t getoffset(void* addr)
Chris@16:    {
Chris@16:       return getoffset(addr, m_pdata->m_data.data());
Chris@16:    }
Chris@16:    std::ptrdiff_t getoffset(const void* addr, const void* base)
Chris@16:    {
Chris@16:       return static_cast<const char*>(addr) - static_cast<const char*>(base);
Chris@16:    }
Chris@16:    re_syntax_base* getaddress(std::ptrdiff_t off)
Chris@16:    {
Chris@16:       return getaddress(off, m_pdata->m_data.data());
Chris@16:    }
Chris@16:    re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
Chris@16:    {
Chris@16:       return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
Chris@16:    }
Chris@16:    void init(unsigned l_flags)
Chris@16:    {
Chris@16:       m_pdata->m_flags = l_flags;
Chris@16:       m_icase = l_flags & regex_constants::icase;
Chris@16:    }
Chris@16:    regbase::flag_type flags()
Chris@16:    {
Chris@16:       return m_pdata->m_flags;
Chris@16:    }
Chris@16:    void flags(regbase::flag_type f)
Chris@16:    {
Chris@16:       m_pdata->m_flags = f;
Chris@16:       if(m_icase != static_cast<bool>(f & regbase::icase))
Chris@16:       {
Chris@16:          m_icase = static_cast<bool>(f & regbase::icase);
Chris@16:       }
Chris@16:    }
Chris@16:    re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
Chris@16:    re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
Chris@16:    re_literal* append_literal(charT c);
Chris@16:    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
Chris@16:    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
Chris@16:    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
Chris@16:    void finalize(const charT* p1, const charT* p2);
Chris@16: protected:
Chris@16:    regex_data<charT, traits>*    m_pdata;              // pointer to the basic_regex_data struct we are filling in
Chris@16:    const ::boost::regex_traits_wrapper<traits>&  
Chris@16:                                  m_traits;             // convenience reference to traits class
Chris@16:    re_syntax_base*               m_last_state;         // the last state we added
Chris@16:    bool                          m_icase;              // true for case insensitive matches
Chris@16:    unsigned                      m_repeater_id;        // the state_id of the next repeater
Chris@16:    bool                          m_has_backrefs;       // true if there are actually any backrefs
Chris@16:    unsigned                      m_backrefs;           // bitmask of permitted backrefs
Chris@16:    boost::uintmax_t              m_bad_repeats;        // bitmask of repeats we can't deduce a startmap for;
Chris@16:    bool                          m_has_recursions;     // set when we have recursive expresisons to fixup
Chris@16:    std::vector<bool>             m_recursion_checks;   // notes which recursions we've followed while analysing this expression
Chris@16:    typename traits::char_class_type m_word_mask;       // mask used to determine if a character is a word character
Chris@16:    typename traits::char_class_type m_mask_space;      // mask used to determine if a character is a word character
Chris@16:    typename traits::char_class_type m_lower_mask;       // mask used to determine if a character is a lowercase character
Chris@16:    typename traits::char_class_type m_upper_mask;      // mask used to determine if a character is an uppercase character
Chris@16:    typename traits::char_class_type m_alpha_mask;      // mask used to determine if a character is an alphabetic character
Chris@16: private:
Chris@16:    basic_regex_creator& operator=(const basic_regex_creator&);
Chris@16:    basic_regex_creator(const basic_regex_creator&);
Chris@16: 
Chris@16:    void fixup_pointers(re_syntax_base* state);
Chris@16:    void fixup_recursions(re_syntax_base* state);
Chris@16:    void create_startmaps(re_syntax_base* state);
Chris@16:    int calculate_backstep(re_syntax_base* state);
Chris@16:    void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
Chris@16:    unsigned get_restart_type(re_syntax_base* state);
Chris@16:    void set_all_masks(unsigned char* bits, unsigned char);
Chris@16:    bool is_bad_repeat(re_syntax_base* pt);
Chris@16:    void set_bad_repeat(re_syntax_base* pt);
Chris@16:    syntax_element_type get_repeat_type(re_syntax_base* state);
Chris@16:    void probe_leading_repeat(re_syntax_base* state);
Chris@16: };
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
Chris@16:    : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_repeater_id(0), m_has_backrefs(false), m_backrefs(0), m_has_recursions(false)
Chris@16: {
Chris@16:    m_pdata->m_data.clear();
Chris@16:    m_pdata->m_status = ::boost::regex_constants::error_ok;
Chris@16:    static const charT w = 'w';
Chris@16:    static const charT s = 's';
Chris@16:    static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
Chris@16:    static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
Chris@16:    static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
Chris@16:    m_word_mask = m_traits.lookup_classname(&w, &w +1);
Chris@16:    m_mask_space = m_traits.lookup_classname(&s, &s +1);
Chris@16:    m_lower_mask = m_traits.lookup_classname(l, l + 5);
Chris@16:    m_upper_mask = m_traits.lookup_classname(u, u + 5);
Chris@16:    m_alpha_mask = m_traits.lookup_classname(a, a + 5);
Chris@16:    m_pdata->m_word_mask = m_word_mask;
Chris@16:    BOOST_ASSERT(m_word_mask != 0); 
Chris@16:    BOOST_ASSERT(m_mask_space != 0); 
Chris@16:    BOOST_ASSERT(m_lower_mask != 0); 
Chris@16:    BOOST_ASSERT(m_upper_mask != 0); 
Chris@16:    BOOST_ASSERT(m_alpha_mask != 0); 
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
Chris@16: {
Chris@16:    // if the state is a backref then make a note of it:
Chris@16:    if(t == syntax_element_backref)
Chris@16:       this->m_has_backrefs = true;
Chris@16:    // append a new state, start by aligning our last one:
Chris@16:    m_pdata->m_data.align();
Chris@16:    // set the offset to the next state in our last one:
Chris@16:    if(m_last_state)
Chris@16:       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
Chris@16:    // now actually extent our data:
Chris@16:    m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
Chris@16:    // fill in boilerplate options in the new state:
Chris@16:    m_last_state->next.i = 0;
Chris@16:    m_last_state->type = t;
Chris@16:    return m_last_state;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
Chris@16: {
Chris@16:    // append a new state, start by aligning our last one:
Chris@16:    m_pdata->m_data.align();
Chris@16:    // set the offset to the next state in our last one:
Chris@16:    if(m_last_state)
Chris@16:       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
Chris@16:    // remember the last state position:
Chris@16:    std::ptrdiff_t off = getoffset(m_last_state) + s;
Chris@16:    // now actually insert our data:
Chris@16:    re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
Chris@16:    // fill in boilerplate options in the new state:
Chris@16:    new_state->next.i = s;
Chris@16:    new_state->type = t;
Chris@16:    m_last_state = getaddress(off);
Chris@16:    return new_state;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
Chris@16: {
Chris@16:    re_literal* result;
Chris@16:    // start by seeing if we have an existing re_literal we can extend:
Chris@16:    if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
Chris@16:    {
Chris@16:       // no existing re_literal, create a new one:
Chris@16:       result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
Chris@16:       result->length = 1;
Chris@16:       *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
Chris@16:    }
Chris@16:    else
Chris@16:    {
Chris@16:       // we have an existing re_literal, extend it:
Chris@16:       std::ptrdiff_t off = getoffset(m_last_state);
Chris@16:       m_pdata->m_data.extend(sizeof(charT));
Chris@16:       m_last_state = result = static_cast<re_literal*>(getaddress(off));
Chris@16:       charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
Chris@16:       characters[result->length] = m_traits.translate(c, m_icase);
Chris@101:       result->length += 1;
Chris@16:    }
Chris@16:    return result;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
Chris@16:    const basic_char_set<charT, traits>& char_set)
Chris@16: {
Chris@16:    typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
Chris@16:    return char_set.has_digraphs() 
Chris@16:       ? append_set(char_set, static_cast<mpl::false_*>(0))
Chris@16:       : append_set(char_set, static_cast<truth_type*>(0));
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: re_syntax_base* basic_regex_creator<charT, traits>::append_set(
Chris@16:    const basic_char_set<charT, traits>& char_set, mpl::false_*)
Chris@16: {
Chris@16:    typedef typename traits::string_type string_type;
Chris@16:    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
Chris@16:    typedef typename traits::char_class_type m_type;
Chris@16:    
Chris@16:    re_set_long<m_type>* result = static_cast<re_set_long<m_type>*>(append_state(syntax_element_long_set, sizeof(re_set_long<m_type>)));
Chris@16:    //
Chris@16:    // fill in the basics:
Chris@16:    //
Chris@16:    result->csingles = static_cast<unsigned int>(::boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end()));
Chris@16:    result->cranges = static_cast<unsigned int>(::boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
Chris@16:    result->cequivalents = static_cast<unsigned int>(::boost::re_detail::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
Chris@16:    result->cclasses = char_set.classes();
Chris@16:    result->cnclasses = char_set.negated_classes();
Chris@16:    if(flags() & regbase::icase)
Chris@16:    {
Chris@16:       // adjust classes as needed:
Chris@16:       if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
Chris@16:          result->cclasses |= m_alpha_mask;
Chris@16:       if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
Chris@16:          result->cnclasses |= m_alpha_mask;
Chris@16:    }
Chris@16: 
Chris@16:    result->isnot = char_set.is_negated();
Chris@16:    result->singleton = !char_set.has_digraphs();
Chris@16:    //
Chris@16:    // remember where the state is for later:
Chris@16:    //
Chris@16:    std::ptrdiff_t offset = getoffset(result);
Chris@16:    //
Chris@16:    // now extend with all the singles:
Chris@16:    //
Chris@16:    item_iterator first, last;
Chris@16:    first = char_set.singles_begin();
Chris@16:    last = char_set.singles_end();
Chris@16:    while(first != last)
Chris@16:    {
Chris@16:       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (first->second ? 3 : 2)));
Chris@16:       p[0] = m_traits.translate(first->first, m_icase);
Chris@16:       if(first->second)
Chris@16:       {
Chris@16:          p[1] = m_traits.translate(first->second, m_icase);
Chris@16:          p[2] = 0;
Chris@16:       }
Chris@16:       else
Chris@16:          p[1] = 0;
Chris@16:       ++first;
Chris@16:    }
Chris@16:    //
Chris@16:    // now extend with all the ranges:
Chris@16:    //
Chris@16:    first = char_set.ranges_begin();
Chris@16:    last = char_set.ranges_end();
Chris@16:    while(first != last)
Chris@16:    {
Chris@16:       // first grab the endpoints of the range:
Chris@16:       digraph<charT> c1 = *first;
Chris@16:       c1.first = this->m_traits.translate(c1.first, this->m_icase);
Chris@16:       c1.second = this->m_traits.translate(c1.second, this->m_icase);
Chris@16:       ++first;
Chris@16:       digraph<charT> c2 = *first;
Chris@16:       c2.first = this->m_traits.translate(c2.first, this->m_icase);
Chris@16:       c2.second = this->m_traits.translate(c2.second, this->m_icase);
Chris@16:       ++first;
Chris@16:       string_type s1, s2;
Chris@16:       // different actions now depending upon whether collation is turned on:
Chris@16:       if(flags() & regex_constants::collate)
Chris@16:       {
Chris@16:          // we need to transform our range into sort keys:
Chris@16:          charT a1[3] = { c1.first, c1.second, charT(0), };
Chris@16:          charT a2[3] = { c2.first, c2.second, charT(0), };
Chris@16:          s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
Chris@16:          s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
Chris@16:          if(s1.size() == 0)
Chris@16:             s1 = string_type(1, charT(0));
Chris@16:          if(s2.size() == 0)
Chris@16:             s2 = string_type(1, charT(0));
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          if(c1.second)
Chris@16:          {
Chris@16:             s1.insert(s1.end(), c1.first);
Chris@16:             s1.insert(s1.end(), c1.second);
Chris@16:          }
Chris@16:          else
Chris@16:             s1 = string_type(1, c1.first);
Chris@16:          if(c2.second)
Chris@16:          {
Chris@16:             s2.insert(s2.end(), c2.first);
Chris@16:             s2.insert(s2.end(), c2.second);
Chris@16:          }
Chris@16:          else
Chris@16:             s2.insert(s2.end(), c2.first);
Chris@16:       }
Chris@16:       if(s1 > s2)
Chris@16:       {
Chris@16:          // Oops error:
Chris@16:          return 0;
Chris@16:       }
Chris@16:       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
Chris@16:       re_detail::copy(s1.begin(), s1.end(), p);
Chris@16:       p[s1.size()] = charT(0);
Chris@16:       p += s1.size() + 1;
Chris@16:       re_detail::copy(s2.begin(), s2.end(), p);
Chris@16:       p[s2.size()] = charT(0);
Chris@16:    }
Chris@16:    //
Chris@16:    // now process the equivalence classes:
Chris@16:    //
Chris@16:    first = char_set.equivalents_begin();
Chris@16:    last = char_set.equivalents_end();
Chris@16:    while(first != last)
Chris@16:    {
Chris@16:       string_type s;
Chris@16:       if(first->second)
Chris@16:       {
Chris@16:          charT cs[3] = { first->first, first->second, charT(0), };
Chris@16:          s = m_traits.transform_primary(cs, cs+2);
Chris@16:       }
Chris@16:       else
Chris@16:          s = m_traits.transform_primary(&first->first, &first->first+1);
Chris@16:       if(s.empty())
Chris@16:          return 0;  // invalid or unsupported equivalence class
Chris@16:       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
Chris@16:       re_detail::copy(s.begin(), s.end(), p);
Chris@16:       p[s.size()] = charT(0);
Chris@16:       ++first;
Chris@16:    }
Chris@16:    //
Chris@16:    // finally reset the address of our last state:
Chris@16:    //
Chris@16:    m_last_state = result = static_cast<re_set_long<m_type>*>(getaddress(offset));
Chris@16:    return result;
Chris@16: }
Chris@16: 
Chris@16: template<class T>
Chris@16: inline bool char_less(T t1, T t2)
Chris@16: {
Chris@16:    return t1 < t2;
Chris@16: }
Chris@16: inline bool char_less(char t1, char t2)
Chris@16: {
Chris@16:    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
Chris@16: }
Chris@16: inline bool char_less(signed char t1, signed char t2)
Chris@16: {
Chris@16:    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: re_syntax_base* basic_regex_creator<charT, traits>::append_set(
Chris@16:    const basic_char_set<charT, traits>& char_set, mpl::true_*)
Chris@16: {
Chris@16:    typedef typename traits::string_type string_type;
Chris@16:    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
Chris@16:    
Chris@16:    re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
Chris@16:    bool negate = char_set.is_negated();
Chris@16:    std::memset(result->_map, 0, sizeof(result->_map));
Chris@16:    //
Chris@16:    // handle singles first:
Chris@16:    //
Chris@16:    item_iterator first, last;
Chris@16:    first = char_set.singles_begin();
Chris@16:    last = char_set.singles_end();
Chris@16:    while(first != last)
Chris@16:    {
Chris@16:       for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
Chris@16:       {
Chris@16:          if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
Chris@16:             == this->m_traits.translate(first->first, this->m_icase))
Chris@16:             result->_map[i] = true;
Chris@16:       }
Chris@16:       ++first;
Chris@16:    }
Chris@16:    //
Chris@16:    // OK now handle ranges:
Chris@16:    //
Chris@16:    first = char_set.ranges_begin();
Chris@16:    last = char_set.ranges_end();
Chris@16:    while(first != last)
Chris@16:    {
Chris@16:       // first grab the endpoints of the range:
Chris@16:       charT c1 = this->m_traits.translate(first->first, this->m_icase);
Chris@16:       ++first;
Chris@16:       charT c2 = this->m_traits.translate(first->first, this->m_icase);
Chris@16:       ++first;
Chris@16:       // different actions now depending upon whether collation is turned on:
Chris@16:       if(flags() & regex_constants::collate)
Chris@16:       {
Chris@16:          // we need to transform our range into sort keys:
Chris@16:          charT c3[2] = { c1, charT(0), };
Chris@16:          string_type s1 = this->m_traits.transform(c3, c3+1);
Chris@16:          c3[0] = c2;
Chris@16:          string_type s2 = this->m_traits.transform(c3, c3+1);
Chris@16:          if(s1 > s2)
Chris@16:          {
Chris@16:             // Oops error:
Chris@16:             return 0;
Chris@16:          }
Chris@16:          BOOST_ASSERT(c3[1] == charT(0));
Chris@16:          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:          {
Chris@16:             c3[0] = static_cast<charT>(i);
Chris@16:             string_type s3 = this->m_traits.transform(c3, c3 +1);
Chris@16:             if((s1 <= s3) && (s3 <= s2))
Chris@16:                result->_map[i] = true;
Chris@16:          }
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          if(char_less(c2, c1))
Chris@16:          {
Chris@16:             // Oops error:
Chris@16:             return 0;
Chris@16:          }
Chris@16:          // everything in range matches:
Chris@16:          std::memset(result->_map + static_cast<unsigned char>(c1), true, 1 + static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1));
Chris@16:       }
Chris@16:    }
Chris@16:    //
Chris@16:    // and now the classes:
Chris@16:    //
Chris@16:    typedef typename traits::char_class_type m_type;
Chris@16:    m_type m = char_set.classes();
Chris@16:    if(flags() & regbase::icase)
Chris@16:    {
Chris@16:       // adjust m as needed:
Chris@16:       if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
Chris@16:          m |= m_alpha_mask;
Chris@16:    }
Chris@16:    if(m != 0)
Chris@16:    {
Chris@16:       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:       {
Chris@16:          if(this->m_traits.isctype(static_cast<charT>(i), m))
Chris@16:             result->_map[i] = true;
Chris@16:       }
Chris@16:    }
Chris@16:    //
Chris@16:    // and now the negated classes:
Chris@16:    //
Chris@16:    m = char_set.negated_classes();
Chris@16:    if(flags() & regbase::icase)
Chris@16:    {
Chris@16:       // adjust m as needed:
Chris@16:       if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
Chris@16:          m |= m_alpha_mask;
Chris@16:    }
Chris@16:    if(m != 0)
Chris@16:    {
Chris@16:       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:       {
Chris@16:          if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
Chris@16:             result->_map[i] = true;
Chris@16:       }
Chris@16:    }
Chris@16:    //
Chris@16:    // now process the equivalence classes:
Chris@16:    //
Chris@16:    first = char_set.equivalents_begin();
Chris@16:    last = char_set.equivalents_end();
Chris@16:    while(first != last)
Chris@16:    {
Chris@16:       string_type s;
Chris@16:       BOOST_ASSERT(static_cast<charT>(0) == first->second);
Chris@16:       s = m_traits.transform_primary(&first->first, &first->first+1);
Chris@16:       if(s.empty())
Chris@16:          return 0;  // invalid or unsupported equivalence class
Chris@16:       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:       {
Chris@16:          charT c[2] = { (static_cast<charT>(i)), charT(0), };
Chris@16:          string_type s2 = this->m_traits.transform_primary(c, c+1);
Chris@16:          if(s == s2)
Chris@16:             result->_map[i] = true;
Chris@16:       }
Chris@16:       ++first;
Chris@16:    }
Chris@16:    if(negate)
Chris@16:    {
Chris@16:       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:       {
Chris@16:          result->_map[i] = !(result->_map[i]);
Chris@16:       }
Chris@16:    }
Chris@16:    return result;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
Chris@16: {
Chris@16:    if(this->m_pdata->m_status)
Chris@16:       return;
Chris@16:    // we've added all the states we need, now finish things off.
Chris@16:    // start by adding a terminating state:
Chris@16:    append_state(syntax_element_match);
Chris@16:    // extend storage to store original expression:
Chris@16:    std::ptrdiff_t len = p2 - p1;
Chris@16:    m_pdata->m_expression_len = len;
Chris@16:    charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
Chris@16:    m_pdata->m_expression = ps;
Chris@16:    re_detail::copy(p1, p2, ps);
Chris@16:    ps[p2 - p1] = 0;
Chris@16:    // fill in our other data...
Chris@16:    // successful parsing implies a zero status:
Chris@16:    m_pdata->m_status = 0;
Chris@16:    // get the first state of the machine:
Chris@16:    m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
Chris@16:    // fixup pointers in the machine:
Chris@16:    fixup_pointers(m_pdata->m_first_state);
Chris@16:    if(m_has_recursions)
Chris@16:    {
Chris@16:       m_pdata->m_has_recursions = true;
Chris@16:       fixup_recursions(m_pdata->m_first_state);
Chris@16:       if(this->m_pdata->m_status)
Chris@16:          return;
Chris@16:    }
Chris@16:    else
Chris@16:       m_pdata->m_has_recursions = false;
Chris@16:    // create nested startmaps:
Chris@16:    create_startmaps(m_pdata->m_first_state);
Chris@16:    // create main startmap:
Chris@16:    std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
Chris@16:    m_pdata->m_can_be_null = 0;
Chris@16: 
Chris@16:    m_bad_repeats = 0;
Chris@16:    if(m_has_recursions)
Chris@16:       m_recursion_checks.assign(1 + m_pdata->m_mark_count, false);
Chris@16:    create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
Chris@16:    // get the restart type:
Chris@16:    m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
Chris@16:    // optimise a leading repeat if there is one:
Chris@16:    probe_leading_repeat(m_pdata->m_first_state);
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
Chris@16: {
Chris@16:    while(state)
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_recurse:
Chris@16:          m_has_recursions = true;
Chris@16:          if(state->next.i)
Chris@16:             state->next.p = getaddress(state->next.i, state);
Chris@16:          else
Chris@16:             state->next.p = 0;
Chris@16:          break;
Chris@16:       case syntax_element_rep:
Chris@16:       case syntax_element_dot_rep:
Chris@16:       case syntax_element_char_rep:
Chris@16:       case syntax_element_short_set_rep:
Chris@16:       case syntax_element_long_set_rep:
Chris@16:          // set the state_id of this repeat:
Chris@16:          static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       case syntax_element_alt:
Chris@16:          std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
Chris@16:          static_cast<re_alt*>(state)->can_be_null = 0;
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       case syntax_element_jump:
Chris@16:          static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       default:
Chris@16:          if(state->next.i)
Chris@16:             state->next.p = getaddress(state->next.i, state);
Chris@16:          else
Chris@16:             state->next.p = 0;
Chris@16:       }
Chris@16:       state = state->next.p;
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
Chris@16: {
Chris@16:    re_syntax_base* base = state;
Chris@16:    while(state)
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_assert_backref:
Chris@16:          {
Chris@16:             // just check that the index is valid:
Chris@16:             int idx = static_cast<const re_brace*>(state)->index;
Chris@16:             if(idx < 0)
Chris@16:             {
Chris@16:                idx = -idx-1;
Chris@16:                if(idx >= 10000)
Chris@16:                {
Chris@16:                   idx = m_pdata->get_id(idx);
Chris@16:                   if(idx <= 0)
Chris@16:                   {
Chris@16:                      // check of sub-expression that doesn't exist:
Chris@16:                      if(0 == this->m_pdata->m_status) // update the error code if not already set
Chris@16:                         this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
Chris@16:                      //
Chris@16:                      // clear the expression, we should be empty:
Chris@16:                      //
Chris@16:                      this->m_pdata->m_expression = 0;
Chris@16:                      this->m_pdata->m_expression_len = 0;
Chris@16:                      //
Chris@16:                      // and throw if required:
Chris@16:                      //
Chris@16:                      if(0 == (this->flags() & regex_constants::no_except))
Chris@16:                      {
Chris@16:                         std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
Chris@16:                         boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
Chris@16:                         e.raise();
Chris@16:                      }
Chris@16:                   }
Chris@16:                }
Chris@16:             }
Chris@16:          }
Chris@16:          break;
Chris@16:       case syntax_element_recurse:
Chris@16:          {
Chris@16:             bool ok = false;
Chris@16:             re_syntax_base* p = base;
Chris@16:             std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
Chris@16:             if(idx > 10000)
Chris@16:             {
Chris@16:                //
Chris@16:                // There may be more than one capture group with this hash, just do what Perl
Chris@16:                // does and recurse to the leftmost:
Chris@16:                //
Chris@16:                idx = m_pdata->get_id(static_cast<int>(idx));
Chris@16:             }
Chris@16:             while(p)
Chris@16:             {
Chris@16:                if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
Chris@16:                {
Chris@16:                   //
Chris@16:                   // We've found the target of the recursion, set the jump target:
Chris@16:                   //
Chris@16:                   static_cast<re_jump*>(state)->alt.p = p;
Chris@16:                   ok = true;
Chris@16:                   // 
Chris@16:                   // Now scan the target for nested repeats:
Chris@16:                   //
Chris@16:                   p = p->next.p;
Chris@16:                   int next_rep_id = 0;
Chris@16:                   while(p)
Chris@16:                   {
Chris@16:                      switch(p->type)
Chris@16:                      {
Chris@16:                      case syntax_element_rep:
Chris@16:                      case syntax_element_dot_rep:
Chris@16:                      case syntax_element_char_rep:
Chris@16:                      case syntax_element_short_set_rep:
Chris@16:                      case syntax_element_long_set_rep:
Chris@16:                         next_rep_id = static_cast<re_repeat*>(p)->state_id;
Chris@16:                         break;
Chris@16:                      case syntax_element_endmark:
Chris@16:                         if(static_cast<const re_brace*>(p)->index == idx)
Chris@16:                            next_rep_id = -1;
Chris@16:                         break;
Chris@16:                      default: 
Chris@16:                         break;
Chris@16:                      }
Chris@16:                      if(next_rep_id)
Chris@16:                         break;
Chris@16:                      p = p->next.p;
Chris@16:                   }
Chris@16:                   if(next_rep_id > 0)
Chris@16:                   {
Chris@16:                      static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
Chris@16:                   }
Chris@16: 
Chris@16:                   break;
Chris@16:                }
Chris@16:                p = p->next.p;
Chris@16:             }
Chris@16:             if(!ok)
Chris@16:             {
Chris@16:                // recursion to sub-expression that doesn't exist:
Chris@16:                if(0 == this->m_pdata->m_status) // update the error code if not already set
Chris@16:                   this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
Chris@16:                //
Chris@16:                // clear the expression, we should be empty:
Chris@16:                //
Chris@16:                this->m_pdata->m_expression = 0;
Chris@16:                this->m_pdata->m_expression_len = 0;
Chris@16:                //
Chris@16:                // and throw if required:
Chris@16:                //
Chris@16:                if(0 == (this->flags() & regex_constants::no_except))
Chris@16:                {
Chris@16:                   std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
Chris@16:                   boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
Chris@16:                   e.raise();
Chris@16:                }
Chris@16:             }
Chris@16:          }
Chris@16:          break;
Chris@16:       default:
Chris@16:          break;
Chris@16:       }
Chris@16:       state = state->next.p;
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
Chris@16: {
Chris@16:    // non-recursive implementation:
Chris@16:    // create the last map in the machine first, so that earlier maps
Chris@16:    // can make use of the result...
Chris@16:    //
Chris@16:    // This was originally a recursive implementation, but that caused stack
Chris@16:    // overflows with complex expressions on small stacks (think COM+).
Chris@16: 
Chris@16:    // start by saving the case setting:
Chris@16:    bool l_icase = m_icase;
Chris@16:    std::vector<std::pair<bool, re_syntax_base*> > v;
Chris@16: 
Chris@16:    while(state)
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_toggle_case:
Chris@16:          // we need to track case changes here:
Chris@16:          m_icase = static_cast<re_case*>(state)->icase;
Chris@16:          state = state->next.p;
Chris@16:          continue;
Chris@16:       case syntax_element_alt:
Chris@16:       case syntax_element_rep:
Chris@16:       case syntax_element_dot_rep:
Chris@16:       case syntax_element_char_rep:
Chris@16:       case syntax_element_short_set_rep:
Chris@16:       case syntax_element_long_set_rep:
Chris@16:          // just push the state onto our stack for now:
Chris@16:          v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
Chris@16:          state = state->next.p;
Chris@16:          break;
Chris@16:       case syntax_element_backstep:
Chris@16:          // we need to calculate how big the backstep is:
Chris@16:          static_cast<re_brace*>(state)->index
Chris@16:             = this->calculate_backstep(state->next.p);
Chris@16:          if(static_cast<re_brace*>(state)->index < 0)
Chris@16:          {
Chris@16:             // Oops error:
Chris@16:             if(0 == this->m_pdata->m_status) // update the error code if not already set
Chris@16:                this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
Chris@16:             //
Chris@16:             // clear the expression, we should be empty:
Chris@16:             //
Chris@16:             this->m_pdata->m_expression = 0;
Chris@16:             this->m_pdata->m_expression_len = 0;
Chris@16:             //
Chris@16:             // and throw if required:
Chris@16:             //
Chris@16:             if(0 == (this->flags() & regex_constants::no_except))
Chris@16:             {
Chris@16:                std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
Chris@16:                boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
Chris@16:                e.raise();
Chris@16:             }
Chris@16:          }
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       default:
Chris@16:          state = state->next.p;
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@16:    // now work through our list, building all the maps as we go:
Chris@16:    while(v.size())
Chris@16:    {
Chris@16:       // Initialize m_recursion_checks if we need it:
Chris@16:       if(m_has_recursions)
Chris@16:          m_recursion_checks.assign(1 + m_pdata->m_mark_count, false);
Chris@16: 
Chris@16:       const std::pair<bool, re_syntax_base*>& p = v.back();
Chris@16:       m_icase = p.first;
Chris@16:       state = p.second;
Chris@16:       v.pop_back();
Chris@16: 
Chris@16:       // Build maps:
Chris@16:       m_bad_repeats = 0;
Chris@16:       create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
Chris@16:       m_bad_repeats = 0;
Chris@16: 
Chris@16:       if(m_has_recursions)
Chris@16:          m_recursion_checks.assign(1 + m_pdata->m_mark_count, false);
Chris@16:       create_startmap(static_cast<re_alt*>(state)->alt.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_skip);
Chris@16:       // adjust the type of the state to allow for faster matching:
Chris@16:       state->type = this->get_repeat_type(state);
Chris@16:    }
Chris@16:    // restore case sensitivity:
Chris@16:    m_icase = l_icase;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
Chris@16: {
Chris@16:    typedef typename traits::char_class_type m_type;
Chris@16:    int result = 0;
Chris@16:    while(state)
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_startmark:
Chris@16:          if((static_cast<re_brace*>(state)->index == -1)
Chris@16:             || (static_cast<re_brace*>(state)->index == -2))
Chris@16:          {
Chris@16:             state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
Chris@16:             continue;
Chris@16:          }
Chris@16:          else if(static_cast<re_brace*>(state)->index == -3)
Chris@16:          {
Chris@16:             state = state->next.p->next.p;
Chris@16:             continue;
Chris@16:          }
Chris@16:          break;
Chris@16:       case syntax_element_endmark:
Chris@16:          if((static_cast<re_brace*>(state)->index == -1)
Chris@16:             || (static_cast<re_brace*>(state)->index == -2))
Chris@16:             return result;
Chris@16:          break;
Chris@16:       case syntax_element_literal:
Chris@16:          result += static_cast<re_literal*>(state)->length;
Chris@16:          break;
Chris@16:       case syntax_element_wild:
Chris@16:       case syntax_element_set:
Chris@16:          result += 1;
Chris@16:          break;
Chris@16:       case syntax_element_dot_rep:
Chris@16:       case syntax_element_char_rep:
Chris@16:       case syntax_element_short_set_rep:
Chris@16:       case syntax_element_backref:
Chris@16:       case syntax_element_rep:
Chris@16:       case syntax_element_combining:
Chris@16:       case syntax_element_long_set_rep:
Chris@16:       case syntax_element_backstep:
Chris@16:          {
Chris@16:             re_repeat* rep = static_cast<re_repeat *>(state);
Chris@16:             // adjust the type of the state to allow for faster matching:
Chris@16:             state->type = this->get_repeat_type(state);
Chris@16:             if((state->type == syntax_element_dot_rep) 
Chris@16:                || (state->type == syntax_element_char_rep)
Chris@16:                || (state->type == syntax_element_short_set_rep))
Chris@16:             {
Chris@16:                if(rep->max != rep->min)
Chris@16:                   return -1;
Chris@16:                result += static_cast<int>(rep->min);
Chris@16:                state = rep->alt.p;
Chris@16:                continue;
Chris@16:             }
Chris@16:             else if(state->type == syntax_element_long_set_rep)
Chris@16:             {
Chris@16:                BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
Chris@16:                if(static_cast<re_set_long<m_type>*>(rep->next.p)->singleton == 0)
Chris@16:                   return -1;
Chris@16:                if(rep->max != rep->min)
Chris@16:                   return -1;
Chris@16:                result += static_cast<int>(rep->min);
Chris@16:                state = rep->alt.p;
Chris@16:                continue;
Chris@16:             }
Chris@16:          }
Chris@16:          return -1;
Chris@16:       case syntax_element_long_set:
Chris@16:          if(static_cast<re_set_long<m_type>*>(state)->singleton == 0)
Chris@16:             return -1;
Chris@16:          result += 1;
Chris@16:          break;
Chris@16:       case syntax_element_jump:
Chris@16:          state = static_cast<re_jump*>(state)->alt.p;
Chris@16:          continue;
Chris@16:       case syntax_element_alt:
Chris@16:          {
Chris@16:             int r1 = calculate_backstep(state->next.p);
Chris@16:             int r2 = calculate_backstep(static_cast<re_alt*>(state)->alt.p);
Chris@16:             if((r1 < 0) || (r1 != r2))
Chris@16:                return -1;
Chris@16:             return result + r1;
Chris@16:          }
Chris@16:       default:
Chris@16:          break;
Chris@16:       }
Chris@16:       state = state->next.p;
Chris@16:    }
Chris@16:    return -1;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
Chris@16: {
Chris@16:    int not_last_jump = 1;
Chris@16:    re_syntax_base* recursion_start = 0;
Chris@16:    int recursion_sub = 0;
Chris@16:    re_syntax_base* recursion_restart = 0;
Chris@16: 
Chris@16:    // track case sensitivity:
Chris@16:    bool l_icase = m_icase;
Chris@16: 
Chris@16:    while(state)
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_toggle_case:
Chris@16:          l_icase = static_cast<re_case*>(state)->icase;
Chris@16:          state = state->next.p;
Chris@16:          break;
Chris@16:       case syntax_element_literal:
Chris@16:       {
Chris@16:          // don't set anything in *pnull, set each element in l_map
Chris@16:          // that could match the first character in the literal:
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             l_map[0] |= mask_init;
Chris@16:             charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
Chris@16:             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:             {
Chris@16:                if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
Chris@16:                   l_map[i] |= mask;
Chris@16:             }
Chris@16:          }
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_end_line:
Chris@16:       {
Chris@16:          // next character must be a line separator (if there is one):
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             l_map[0] |= mask_init;
Chris@16:             l_map[static_cast<unsigned>('\n')] |= mask;
Chris@16:             l_map[static_cast<unsigned>('\r')] |= mask;
Chris@16:             l_map[static_cast<unsigned>('\f')] |= mask;
Chris@16:             l_map[0x85] |= mask;
Chris@16:          }
Chris@16:          // now figure out if we can match a NULL string at this point:
Chris@16:          if(pnull)
Chris@16:             create_startmap(state->next.p, 0, pnull, mask);
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_recurse:
Chris@16:          {
Chris@16:             if(state->type == syntax_element_startmark)
Chris@16:                recursion_sub = static_cast<re_brace*>(state)->index;
Chris@16:             else
Chris@16:                recursion_sub = 0;
Chris@16:             if(m_recursion_checks[recursion_sub])
Chris@16:             {
Chris@16:                // Infinite recursion!!
Chris@16:                if(0 == this->m_pdata->m_status) // update the error code if not already set
Chris@16:                   this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
Chris@16:                //
Chris@16:                // clear the expression, we should be empty:
Chris@16:                //
Chris@16:                this->m_pdata->m_expression = 0;
Chris@16:                this->m_pdata->m_expression_len = 0;
Chris@16:                //
Chris@16:                // and throw if required:
Chris@16:                //
Chris@16:                if(0 == (this->flags() & regex_constants::no_except))
Chris@16:                {
Chris@16:                   std::string message = "Encountered an infinite recursion.";
Chris@16:                   boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
Chris@16:                   e.raise();
Chris@16:                }
Chris@16:             }
Chris@16:             else if(recursion_start == 0)
Chris@16:             {
Chris@16:                recursion_start = state;
Chris@16:                recursion_restart = state->next.p;
Chris@16:                state = static_cast<re_jump*>(state)->alt.p;
Chris@16:                m_recursion_checks[recursion_sub] = true;
Chris@16:                break;
Chris@16:             }
Chris@16:             m_recursion_checks[recursion_sub] = true;
Chris@16:             // can't handle nested recursion here...
Chris@16:             BOOST_FALLTHROUGH;
Chris@16:          }
Chris@16:       case syntax_element_backref:
Chris@16:          // can be null, and any character can match:
Chris@16:          if(pnull)
Chris@16:             *pnull |= mask;
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       case syntax_element_wild:
Chris@16:       {
Chris@16:          // can't be null, any character can match:
Chris@16:          set_all_masks(l_map, mask);
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_match:
Chris@16:       {
Chris@16:          // must be null, any character can match:
Chris@16:          set_all_masks(l_map, mask);
Chris@16:          if(pnull)
Chris@16:             *pnull |= mask;
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_word_start:
Chris@16:       {
Chris@16:          // recurse, then AND with all the word characters:
Chris@16:          create_startmap(state->next.p, l_map, pnull, mask);
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             l_map[0] |= mask_init;
Chris@16:             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:             {
Chris@16:                if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
Chris@16:                   l_map[i] &= static_cast<unsigned char>(~mask);
Chris@16:             }
Chris@16:          }
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_word_end:
Chris@16:       {
Chris@16:          // recurse, then AND with all the word characters:
Chris@16:          create_startmap(state->next.p, l_map, pnull, mask);
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             l_map[0] |= mask_init;
Chris@16:             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:             {
Chris@16:                if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
Chris@16:                   l_map[i] &= static_cast<unsigned char>(~mask);
Chris@16:             }
Chris@16:          }
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_buffer_end:
Chris@16:       {
Chris@16:          // we *must be null* :
Chris@16:          if(pnull)
Chris@16:             *pnull |= mask;
Chris@16:          return;
Chris@16:       }
Chris@16:       case syntax_element_long_set:
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             typedef typename traits::char_class_type m_type;
Chris@16:             if(static_cast<re_set_long<m_type>*>(state)->singleton)
Chris@16:             {
Chris@16:                l_map[0] |= mask_init;
Chris@16:                for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:                {
Chris@16:                   charT c = static_cast<charT>(i);
Chris@16:                   if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<m_type>*>(state), *m_pdata, l_icase))
Chris@16:                      l_map[i] |= mask;
Chris@16:                }
Chris@16:             }
Chris@16:             else
Chris@16:                set_all_masks(l_map, mask);
Chris@16:          }
Chris@16:          return;
Chris@16:       case syntax_element_set:
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             l_map[0] |= mask_init;
Chris@16:             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:             {
Chris@16:                if(static_cast<re_set*>(state)->_map[
Chris@16:                   static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
Chris@16:                   l_map[i] |= mask;
Chris@16:             }
Chris@16:          }
Chris@16:          return;
Chris@16:       case syntax_element_jump:
Chris@16:          // take the jump:
Chris@16:          state = static_cast<re_alt*>(state)->alt.p;
Chris@16:          not_last_jump = -1;
Chris@16:          break;
Chris@16:       case syntax_element_alt:
Chris@16:       case syntax_element_rep:
Chris@16:       case syntax_element_dot_rep:
Chris@16:       case syntax_element_char_rep:
Chris@16:       case syntax_element_short_set_rep:
Chris@16:       case syntax_element_long_set_rep:
Chris@16:          {
Chris@16:             re_alt* rep = static_cast<re_alt*>(state);
Chris@16:             if(rep->_map[0] & mask_init)
Chris@16:             {
Chris@16:                if(l_map)
Chris@16:                {
Chris@16:                   // copy previous results:
Chris@16:                   l_map[0] |= mask_init;
Chris@16:                   for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
Chris@16:                   {
Chris@16:                      if(rep->_map[i] & mask_any)
Chris@16:                         l_map[i] |= mask;
Chris@16:                   }
Chris@16:                }
Chris@16:                if(pnull)
Chris@16:                {
Chris@16:                   if(rep->can_be_null & mask_any)
Chris@16:                      *pnull |= mask;
Chris@16:                }
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16:                // we haven't created a startmap for this alternative yet
Chris@16:                // so take the union of the two options:
Chris@16:                if(is_bad_repeat(state))
Chris@16:                {
Chris@16:                   set_all_masks(l_map, mask);
Chris@16:                   if(pnull)
Chris@16:                      *pnull |= mask;
Chris@16:                   return;
Chris@16:                }
Chris@16:                set_bad_repeat(state);
Chris@16:                create_startmap(state->next.p, l_map, pnull, mask);
Chris@16:                if((state->type == syntax_element_alt)
Chris@16:                   || (static_cast<re_repeat*>(state)->min == 0)
Chris@16:                   || (not_last_jump == 0))
Chris@16:                   create_startmap(rep->alt.p, l_map, pnull, mask);
Chris@16:             }
Chris@16:          }
Chris@16:          return;
Chris@16:       case syntax_element_soft_buffer_end:
Chris@16:          // match newline or null:
Chris@16:          if(l_map)
Chris@16:          {
Chris@16:             l_map[0] |= mask_init;
Chris@16:             l_map[static_cast<unsigned>('\n')] |= mask;
Chris@16:             l_map[static_cast<unsigned>('\r')] |= mask;
Chris@16:          }
Chris@16:          if(pnull)
Chris@16:             *pnull |= mask;
Chris@16:          return;
Chris@16:       case syntax_element_endmark:
Chris@16:          // need to handle independent subs as a special case:
Chris@16:          if(static_cast<re_brace*>(state)->index < 0)
Chris@16:          {
Chris@16:             // can be null, any character can match:
Chris@16:             set_all_masks(l_map, mask);
Chris@16:             if(pnull)
Chris@16:                *pnull |= mask;
Chris@16:             return;
Chris@16:          }
Chris@16:          else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
Chris@16:          {
Chris@16:             // recursion termination:
Chris@16:             recursion_start = 0;
Chris@16:             state = recursion_restart;
Chris@16:             break;
Chris@16:          }
Chris@16: 
Chris@16:          //
Chris@16:          // Normally we just go to the next state... but if this sub-expression is
Chris@16:          // the target of a recursion, then we might be ending a recursion, in which
Chris@16:          // case we should check whatever follows that recursion, as well as whatever
Chris@16:          // follows this state:
Chris@16:          //
Chris@16:          if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
Chris@16:          {
Chris@16:             bool ok = false;
Chris@16:             re_syntax_base* p = m_pdata->m_first_state;
Chris@16:             while(p)
Chris@16:             {
Chris@16:                if(p->type == syntax_element_recurse)
Chris@16:                {
Chris@16:                   re_brace* p2 = static_cast<re_brace*>(static_cast<re_jump*>(p)->alt.p);
Chris@16:                   if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
Chris@16:                   {
Chris@16:                      ok = true;
Chris@16:                      break;
Chris@16:                   }
Chris@16:                }
Chris@16:                p = p->next.p;
Chris@16:             }
Chris@16:             if(ok)
Chris@16:             {
Chris@16:                create_startmap(p->next.p, l_map, pnull, mask);
Chris@16:             }
Chris@16:          }
Chris@16:          state = state->next.p;
Chris@16:          break;
Chris@16: 
Chris@16:       case syntax_element_startmark:
Chris@16:          // need to handle independent subs as a special case:
Chris@16:          if(static_cast<re_brace*>(state)->index == -3)
Chris@16:          {
Chris@16:             state = state->next.p->next.p;
Chris@16:             break;
Chris@16:          }
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       default:
Chris@16:          state = state->next.p;
Chris@16:       }
Chris@16:       ++not_last_jump;
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
Chris@16: {
Chris@16:    //
Chris@16:    // find out how the machine starts, so we can optimise the search:
Chris@16:    //
Chris@16:    while(state)
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_startmark:
Chris@16:       case syntax_element_endmark:
Chris@16:          state = state->next.p;
Chris@16:          continue;
Chris@16:       case syntax_element_start_line:
Chris@16:          return regbase::restart_line;
Chris@16:       case syntax_element_word_start:
Chris@16:          return regbase::restart_word;
Chris@16:       case syntax_element_buffer_start:
Chris@16:          return regbase::restart_buf;
Chris@16:       case syntax_element_restart_continue:
Chris@16:          return regbase::restart_continue;
Chris@16:       default:
Chris@16:          state = 0;
Chris@16:          continue;
Chris@16:       }
Chris@16:    }
Chris@16:    return regbase::restart_any;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
Chris@16: {
Chris@16:    //
Chris@16:    // set mask in all of bits elements, 
Chris@16:    // if bits[0] has mask_init not set then we can 
Chris@16:    // optimise this to a call to memset:
Chris@16:    //
Chris@16:    if(bits)
Chris@16:    {
Chris@16:       if(bits[0] == 0)
Chris@16:          (std::memset)(bits, mask, 1u << CHAR_BIT);
Chris@16:       else
Chris@16:       {
Chris@16:          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
Chris@16:             bits[i] |= mask;
Chris@16:       }
Chris@16:       bits[0] |= mask_init;
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
Chris@16: {
Chris@16:    switch(pt->type)
Chris@16:    {
Chris@16:    case syntax_element_rep:
Chris@16:    case syntax_element_dot_rep:
Chris@16:    case syntax_element_char_rep:
Chris@16:    case syntax_element_short_set_rep:
Chris@16:    case syntax_element_long_set_rep:
Chris@16:       {
Chris@16:          unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
Chris@16:          if(state_id > sizeof(m_bad_repeats) * CHAR_BIT)
Chris@16:             return true;  // run out of bits, assume we can't traverse this one.
Chris@16:          static const boost::uintmax_t one = 1uL;
Chris@16:          return m_bad_repeats & (one << state_id);
Chris@16:       }
Chris@16:    default:
Chris@16:       return false;
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
Chris@16: {
Chris@16:    switch(pt->type)
Chris@16:    {
Chris@16:    case syntax_element_rep:
Chris@16:    case syntax_element_dot_rep:
Chris@16:    case syntax_element_char_rep:
Chris@16:    case syntax_element_short_set_rep:
Chris@16:    case syntax_element_long_set_rep:
Chris@16:       {
Chris@16:          unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
Chris@16:          static const boost::uintmax_t one = 1uL;
Chris@16:          if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
Chris@16:             m_bad_repeats |= (one << state_id);
Chris@16:       }
Chris@16:       break;
Chris@16:    default:
Chris@16:       break;
Chris@16:    }
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
Chris@16: {
Chris@16:    typedef typename traits::char_class_type m_type;
Chris@16:    if(state->type == syntax_element_rep)
Chris@16:    {
Chris@16:       // check to see if we are repeating a single state:
Chris@16:       if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
Chris@16:       {
Chris@16:          switch(state->next.p->type)
Chris@16:          {
Chris@16:          case re_detail::syntax_element_wild:
Chris@16:             return re_detail::syntax_element_dot_rep;
Chris@16:          case re_detail::syntax_element_literal:
Chris@16:             return re_detail::syntax_element_char_rep;
Chris@16:          case re_detail::syntax_element_set:
Chris@16:             return re_detail::syntax_element_short_set_rep;
Chris@16:          case re_detail::syntax_element_long_set:
Chris@16:             if(static_cast<re_detail::re_set_long<m_type>*>(state->next.p)->singleton)
Chris@16:                return re_detail::syntax_element_long_set_rep;
Chris@16:             break;
Chris@16:          default:
Chris@16:             break;
Chris@16:          }
Chris@16:       }
Chris@16:    }
Chris@16:    return state->type;
Chris@16: }
Chris@16: 
Chris@16: template <class charT, class traits>
Chris@16: void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
Chris@16: {
Chris@16:    // enumerate our states, and see if we have a leading repeat 
Chris@16:    // for which failed search restarts can be optimised;
Chris@16:    do
Chris@16:    {
Chris@16:       switch(state->type)
Chris@16:       {
Chris@16:       case syntax_element_startmark:
Chris@16:          if(static_cast<re_brace*>(state)->index >= 0)
Chris@16:          {
Chris@16:             state = state->next.p;
Chris@16:             continue;
Chris@16:          }
Chris@16:          if((static_cast<re_brace*>(state)->index == -1)
Chris@16:             || (static_cast<re_brace*>(state)->index == -2))
Chris@16:          {
Chris@16:             // skip past the zero width assertion:
Chris@16:             state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
Chris@16:             continue;
Chris@16:          }
Chris@16:          if(static_cast<re_brace*>(state)->index == -3)
Chris@16:          {
Chris@16:             // Have to skip the leading jump state:
Chris@16:             state = state->next.p->next.p;
Chris@16:             continue;
Chris@16:          }
Chris@16:          return;
Chris@16:       case syntax_element_endmark:
Chris@16:       case syntax_element_start_line:
Chris@16:       case syntax_element_end_line:
Chris@16:       case syntax_element_word_boundary:
Chris@16:       case syntax_element_within_word:
Chris@16:       case syntax_element_word_start:
Chris@16:       case syntax_element_word_end:
Chris@16:       case syntax_element_buffer_start:
Chris@16:       case syntax_element_buffer_end:
Chris@16:       case syntax_element_restart_continue:
Chris@16:          state = state->next.p;
Chris@16:          break;
Chris@16:       case syntax_element_dot_rep:
Chris@16:       case syntax_element_char_rep:
Chris@16:       case syntax_element_short_set_rep:
Chris@16:       case syntax_element_long_set_rep:
Chris@16:          if(this->m_has_backrefs == 0)
Chris@16:             static_cast<re_repeat*>(state)->leading = true;
Chris@16:          BOOST_FALLTHROUGH;
Chris@16:       default:
Chris@16:          return;
Chris@16:       }
Chris@16:    }while(state);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } // namespace re_detail
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #ifdef BOOST_MSVC
Chris@16: #  pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(push)
Chris@16: #pragma warning(disable: 4103)
Chris@16: #endif
Chris@16: #ifdef BOOST_HAS_ABI_HEADERS
Chris@16: #  include BOOST_ABI_SUFFIX
Chris@16: #endif
Chris@16: #ifdef BOOST_MSVC
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: #endif
Chris@16: