regex/v4/basic_regex_creator.hpp

0001 /*
0002  *
0003  * Copyright (c) 2004
0004  * John Maddock
0005  *
0006  * Use, modification and distribution are subject to the
0007  * Boost Software License, Version 1.0. (See accompanying file
0008  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0009  *
0010  */
0011
0012  /*
0013   *   LOCATION:    see http://www.boost.org for most recent version.
0014   *   FILE         basic_regex_creator.cpp
0015   *   VERSION      see <boost/version.hpp>
0016   *   DESCRIPTION: Declares template class basic_regex_creator which fills in
0017   *                the data members of a regex_data object.
0018   */
0019
0020 #ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
0021 #define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
0022
0023 #include <boost/regex/v4/indexed_bit_flag.hpp>
0024
0025 #ifdef BOOST_MSVC
0026 #pragma warning(push)
0027 #pragma warning(disable: 4103)
0028 #endif
0029 #ifdef BOOST_HAS_ABI_HEADERS
0030 #  include BOOST_ABI_PREFIX
0031 #endif
0032 #ifdef BOOST_MSVC
0033 #pragma warning(pop)
0034 #endif
0035
0036 #ifdef BOOST_MSVC
0037 #  pragma warning(push)
0038 #if BOOST_MSVC < 1910
0039 #pragma warning(disable:4800)
0040 #endif
0041 #endif
0042
0043 namespace boost{
0044
0045 namespace BOOST_REGEX_DETAIL_NS{
0046
0047 template <class charT>
0048 struct digraph : public std::pair<charT, charT>
0049 {
0050    digraph() : std::pair<charT, charT>(charT(0), charT(0)){}
0051    digraph(charT c1) : std::pair<charT, charT>(c1, charT(0)){}
0052    digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
0053    {}
0054    digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
0055 #ifndef BOOST_NO_CXX11_DEFAULTED_FUNCTIONS
0056    digraph<charT>& operator=(const digraph<charT>&) = default;
0057 #endif
0058    template <class Seq>
0059    digraph(const Seq& s) : std::pair<charT, charT>()
0060    {
0061       BOOST_REGEX_ASSERT(s.size() <= 2);
0062       BOOST_REGEX_ASSERT(s.size());
0063       this->first = s[0];
0064       this->second = (s.size() > 1) ? s[1] : 0;
0065    }
0066 };
0067
0068 template <class charT, class traits>
0069 class basic_char_set
0070 {
0071 public:
0072    typedef digraph<charT>                   digraph_type;
0073    typedef typename traits::string_type     string_type;
0074    typedef typename traits::char_class_type m_type;
0075
0076    basic_char_set()
0077    {
0078       m_negate = false;
0079       m_has_digraphs = false;
0080       m_classes = 0;
0081       m_negated_classes = 0;
0082       m_empty = true;
0083    }
0084
0085    void add_single(const digraph_type& s)
0086    {
0087       m_singles.insert(s);
0088       if(s.second)
0089          m_has_digraphs = true;
0090       m_empty = false;
0091    }
0092    void add_range(const digraph_type& first, const digraph_type& end)
0093    {
0094       m_ranges.push_back(first);
0095       m_ranges.push_back(end);
0096       if(first.second)
0097       {
0098          m_has_digraphs = true;
0099          add_single(first);
0100       }
0101       if(end.second)
0102       {
0103          m_has_digraphs = true;
0104          add_single(end);
0105       }
0106       m_empty = false;
0107    }
0108    void add_class(m_type m)
0109    {
0110       m_classes |= m;
0111       m_empty = false;
0112    }
0113    void add_negated_class(m_type m)
0114    {
0115       m_negated_classes |= m;
0116       m_empty = false;
0117    }
0118    void add_equivalent(const digraph_type& s)
0119    {
0120       m_equivalents.insert(s);
0121       if(s.second)
0122       {
0123          m_has_digraphs = true;
0124          add_single(s);
0125       }
0126       m_empty = false;
0127    }
0128    void negate()
0129    {
0130       m_negate = true;
0131       //m_empty = false;
0132    }
0133
0134    //
0135    // accessor functions:
0136    //
0137    bool has_digraphs()const
0138    {
0139       return m_has_digraphs;
0140    }
0141    bool is_negated()const
0142    {
0143       return m_negate;
0144    }
0145    typedef typename std::vector<digraph_type>::const_iterator  list_iterator;
0146    typedef typename std::set<digraph_type>::const_iterator     set_iterator;
0147    set_iterator singles_begin()const
0148    {
0149       return m_singles.begin();
0150    }
0151    set_iterator singles_end()const
0152    {
0153       return m_singles.end();
0154    }
0155    list_iterator ranges_begin()const
0156    {
0157       return m_ranges.begin();
0158    }
0159    list_iterator ranges_end()const
0160    {
0161       return m_ranges.end();
0162    }
0163    set_iterator equivalents_begin()const
0164    {
0165       return m_equivalents.begin();
0166    }
0167    set_iterator equivalents_end()const
0168    {
0169       return m_equivalents.end();
0170    }
0171    m_type classes()const
0172    {
0173       return m_classes;
0174    }
0175    m_type negated_classes()const
0176    {
0177       return m_negated_classes;
0178    }
0179    bool empty()const
0180    {
0181       return m_empty;
0182    }
0183 private:
0184    std::set<digraph_type>    m_singles;         // a list of single characters to match
0185    std::vector<digraph_type> m_ranges;          // a list of end points of our ranges
0186    bool                      m_negate;          // true if the set is to be negated
0187    bool                      m_has_digraphs;    // true if we have digraphs present
0188    m_type                    m_classes;         // character classes to match
0189    m_type                    m_negated_classes; // negated character classes to match
0190    bool                      m_empty;           // whether we've added anything yet
0191    std::set<digraph_type>    m_equivalents;     // a list of equivalence classes
0192 };
0193
0194 template <class charT, class traits>
0195 class basic_regex_creator
0196 {
0197 public:
0198    basic_regex_creator(regex_data<charT, traits>* data);
0199    std::ptrdiff_t getoffset(void* addr)
0200    {
0201       return getoffset(addr, m_pdata->m_data.data());
0202    }
0203    std::ptrdiff_t getoffset(const void* addr, const void* base)
0204    {
0205       return static_cast<const char*>(addr) - static_cast<const char*>(base);
0206    }
0207    re_syntax_base* getaddress(std::ptrdiff_t off)
0208    {
0209       return getaddress(off, m_pdata->m_data.data());
0210    }
0211    re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
0212    {
0213       return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
0214    }
0215    void init(unsigned l_flags)
0216    {
0217       m_pdata->m_flags = l_flags;
0218       m_icase = l_flags & regex_constants::icase;
0219    }
0220    regbase::flag_type flags()
0221    {
0222       return m_pdata->m_flags;
0223    }
0224    void flags(regbase::flag_type f)
0225    {
0226       m_pdata->m_flags = f;
0227       if(m_icase != static_cast<bool>(f & regbase::icase))
0228       {
0229          m_icase = static_cast<bool>(f & regbase::icase);
0230       }
0231    }
0232    re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
0233    re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
0234    re_literal* append_literal(charT c);
0235    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
0236    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
0237    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
0238    void finalize(const charT* p1, const charT* p2);
0239 protected:
0240    regex_data<charT, traits>*    m_pdata;              // pointer to the basic_regex_data struct we are filling in
0241    const ::boost::regex_traits_wrapper<traits>&
0242                                  m_traits;             // convenience reference to traits class
0243    re_syntax_base*               m_last_state;         // the last state we added
0244    bool                          m_icase;              // true for case insensitive matches
0245    unsigned                      m_repeater_id;        // the state_id of the next repeater
0246    bool                          m_has_backrefs;       // true if there are actually any backrefs
0247    indexed_bit_flag              m_backrefs;           // bitmask of permitted backrefs
0248    boost::uintmax_t              m_bad_repeats;        // bitmask of repeats we can't deduce a startmap for;
0249    bool                          m_has_recursions;     // set when we have recursive expressions to fixup
0250    std::vector<unsigned char>    m_recursion_checks;   // notes which recursions we've followed while analysing this expression
0251    typename traits::char_class_type m_word_mask;       // mask used to determine if a character is a word character
0252    typename traits::char_class_type m_mask_space;      // mask used to determine if a character is a word character
0253    typename traits::char_class_type m_lower_mask;       // mask used to determine if a character is a lowercase character
0254    typename traits::char_class_type m_upper_mask;      // mask used to determine if a character is an uppercase character
0255    typename traits::char_class_type m_alpha_mask;      // mask used to determine if a character is an alphabetic character
0256 private:
0257    basic_regex_creator& operator=(const basic_regex_creator&);
0258    basic_regex_creator(const basic_regex_creator&);
0259
0260    void fixup_pointers(re_syntax_base* state);
0261    void fixup_recursions(re_syntax_base* state);
0262    void create_startmaps(re_syntax_base* state);
0263    int calculate_backstep(re_syntax_base* state);
0264    void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
0265    unsigned get_restart_type(re_syntax_base* state);
0266    void set_all_masks(unsigned char* bits, unsigned char);
0267    bool is_bad_repeat(re_syntax_base* pt);
0268    void set_bad_repeat(re_syntax_base* pt);
0269    syntax_element_type get_repeat_type(re_syntax_base* state);
0270    void probe_leading_repeat(re_syntax_base* state);
0271 };
0272
0273 template <class charT, class traits>
0274 basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
0275    : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_icase(false), m_repeater_id(0),
0276    m_has_backrefs(false), m_bad_repeats(0), m_has_recursions(false), m_word_mask(0), m_mask_space(0), m_lower_mask(0), m_upper_mask(0), m_alpha_mask(0)
0277 {
0278    m_pdata->m_data.clear();
0279    m_pdata->m_status = ::boost::regex_constants::error_ok;
0280    static const charT w = 'w';
0281    static const charT s = 's';
0282    static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
0283    static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
0284    static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
0285    m_word_mask = m_traits.lookup_classname(&w, &w +1);
0286    m_mask_space = m_traits.lookup_classname(&s, &s +1);
0287    m_lower_mask = m_traits.lookup_classname(l, l + 5);
0288    m_upper_mask = m_traits.lookup_classname(u, u + 5);
0289    m_alpha_mask = m_traits.lookup_classname(a, a + 5);
0290    m_pdata->m_word_mask = m_word_mask;
0291    BOOST_REGEX_ASSERT(m_word_mask != 0);
0292    BOOST_REGEX_ASSERT(m_mask_space != 0);
0293    BOOST_REGEX_ASSERT(m_lower_mask != 0);
0294    BOOST_REGEX_ASSERT(m_upper_mask != 0);
0295    BOOST_REGEX_ASSERT(m_alpha_mask != 0);
0296 }
0297
0298 template <class charT, class traits>
0299 re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
0300 {
0301    // if the state is a backref then make a note of it:
0302    if(t == syntax_element_backref)
0303       this->m_has_backrefs = true;
0304    // append a new state, start by aligning our last one:
0305    m_pdata->m_data.align();
0306    // set the offset to the next state in our last one:
0307    if(m_last_state)
0308       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
0309    // now actually extend our data:
0310    m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
0311    // fill in boilerplate options in the new state:
0312    m_last_state->next.i = 0;
0313    m_last_state->type = t;
0314    return m_last_state;
0315 }
0316
0317 template <class charT, class traits>
0318 re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
0319 {
0320    // append a new state, start by aligning our last one:
0321    m_pdata->m_data.align();
0322    // set the offset to the next state in our last one:
0323    if(m_last_state)
0324       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
0325    // remember the last state position:
0326    std::ptrdiff_t off = getoffset(m_last_state) + s;
0327    // now actually insert our data:
0328    re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
0329    // fill in boilerplate options in the new state:
0330    new_state->next.i = s;
0331    new_state->type = t;
0332    m_last_state = getaddress(off);
0333    return new_state;
0334 }
0335
0336 template <class charT, class traits>
0337 re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
0338 {
0339    re_literal* result;
0340    // start by seeing if we have an existing re_literal we can extend:
0341    if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
0342    {
0343       // no existing re_literal, create a new one:
0344       result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
0345       result->length = 1;
0346       *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
0347    }
0348    else
0349    {
0350       // we have an existing re_literal, extend it:
0351       std::ptrdiff_t off = getoffset(m_last_state);
0352       m_pdata->m_data.extend(sizeof(charT));
0353       m_last_state = result = static_cast<re_literal*>(getaddress(off));
0354       charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
0355       characters[result->length] = m_traits.translate(c, m_icase);
0356       result->length += 1;
0357    }
0358    return result;
0359 }
0360
0361 template <class charT, class traits>
0362 inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
0363    const basic_char_set<charT, traits>& char_set)
0364 {
0365    typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
0366    return char_set.has_digraphs()
0367       ? append_set(char_set, static_cast<mpl::false_*>(0))
0368       : append_set(char_set, static_cast<truth_type*>(0));
0369 }
0370
0371 template <class charT, class traits>
0372 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
0373    const basic_char_set<charT, traits>& char_set, mpl::false_*)
0374 {
0375    typedef typename traits::string_type string_type;
0376    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
0377    typedef typename basic_char_set<charT, traits>::set_iterator  set_iterator;
0378    typedef typename traits::char_class_type m_type;
0379
0380    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>)));
0381    //
0382    // fill in the basics:
0383    //
0384    result->csingles = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.singles_begin(), char_set.singles_end()));
0385    result->cranges = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
0386    result->cequivalents = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
0387    result->cclasses = char_set.classes();
0388    result->cnclasses = char_set.negated_classes();
0389    if(flags() & regbase::icase)
0390    {
0391       // adjust classes as needed:
0392       if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
0393          result->cclasses |= m_alpha_mask;
0394       if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
0395          result->cnclasses |= m_alpha_mask;
0396    }
0397
0398    result->isnot = char_set.is_negated();
0399    result->singleton = !char_set.has_digraphs();
0400    //
0401    // remember where the state is for later:
0402    //
0403    std::ptrdiff_t offset = getoffset(result);
0404    //
0405    // now extend with all the singles:
0406    //
0407    item_iterator first, last;
0408    set_iterator sfirst, slast;
0409    sfirst = char_set.singles_begin();
0410    slast = char_set.singles_end();
0411    while(sfirst != slast)
0412    {
0413       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (sfirst->first == static_cast<charT>(0) ? 1 : sfirst->second ? 3 : 2)));
0414       p[0] = m_traits.translate(sfirst->first, m_icase);
0415       if(sfirst->first == static_cast<charT>(0))
0416       {
0417          p[0] = 0;
0418       }
0419       else if(sfirst->second)
0420       {
0421          p[1] = m_traits.translate(sfirst->second, m_icase);
0422          p[2] = 0;
0423       }
0424       else
0425          p[1] = 0;
0426       ++sfirst;
0427    }
0428    //
0429    // now extend with all the ranges:
0430    //
0431    first = char_set.ranges_begin();
0432    last = char_set.ranges_end();
0433    while(first != last)
0434    {
0435       // first grab the endpoints of the range:
0436       digraph<charT> c1 = *first;
0437       c1.first = this->m_traits.translate(c1.first, this->m_icase);
0438       c1.second = this->m_traits.translate(c1.second, this->m_icase);
0439       ++first;
0440       digraph<charT> c2 = *first;
0441       c2.first = this->m_traits.translate(c2.first, this->m_icase);
0442       c2.second = this->m_traits.translate(c2.second, this->m_icase);
0443       ++first;
0444       string_type s1, s2;
0445       // different actions now depending upon whether collation is turned on:
0446       if(flags() & regex_constants::collate)
0447       {
0448          // we need to transform our range into sort keys:
0449          charT a1[3] = { c1.first, c1.second, charT(0), };
0450          charT a2[3] = { c2.first, c2.second, charT(0), };
0451          s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
0452          s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
0453          if(s1.empty())
0454             s1 = string_type(1, charT(0));
0455          if(s2.empty())
0456             s2 = string_type(1, charT(0));
0457       }
0458       else
0459       {
0460          if(c1.second)
0461          {
0462             s1.insert(s1.end(), c1.first);
0463             s1.insert(s1.end(), c1.second);
0464          }
0465          else
0466             s1 = string_type(1, c1.first);
0467          if(c2.second)
0468          {
0469             s2.insert(s2.end(), c2.first);
0470             s2.insert(s2.end(), c2.second);
0471          }
0472          else
0473             s2.insert(s2.end(), c2.first);
0474       }
0475       if(s1 > s2)
0476       {
0477          // Oops error:
0478          return 0;
0479       }
0480       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
0481       BOOST_REGEX_DETAIL_NS::copy(s1.begin(), s1.end(), p);
0482       p[s1.size()] = charT(0);
0483       p += s1.size() + 1;
0484       BOOST_REGEX_DETAIL_NS::copy(s2.begin(), s2.end(), p);
0485       p[s2.size()] = charT(0);
0486    }
0487    //
0488    // now process the equivalence classes:
0489    //
0490    sfirst = char_set.equivalents_begin();
0491    slast = char_set.equivalents_end();
0492    while(sfirst != slast)
0493    {
0494       string_type s;
0495       if(sfirst->second)
0496       {
0497          charT cs[3] = { sfirst->first, sfirst->second, charT(0), };
0498          s = m_traits.transform_primary(cs, cs+2);
0499       }
0500       else
0501          s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
0502       if(s.empty())
0503          return 0;  // invalid or unsupported equivalence class
0504       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
0505       BOOST_REGEX_DETAIL_NS::copy(s.begin(), s.end(), p);
0506       p[s.size()] = charT(0);
0507       ++sfirst;
0508    }
0509    //
0510    // finally reset the address of our last state:
0511    //
0512    m_last_state = result = static_cast<re_set_long<m_type>*>(getaddress(offset));
0513    return result;
0514 }
0515
0516 template<class T>
0517 inline bool char_less(T t1, T t2)
0518 {
0519    return t1 < t2;
0520 }
0521 inline bool char_less(char t1, char t2)
0522 {
0523    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
0524 }
0525 inline bool char_less(signed char t1, signed char t2)
0526 {
0527    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
0528 }
0529
0530 template <class charT, class traits>
0531 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
0532    const basic_char_set<charT, traits>& char_set, mpl::true_*)
0533 {
0534    typedef typename traits::string_type string_type;
0535    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
0536    typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
0537
0538    re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
0539    bool negate = char_set.is_negated();
0540    std::memset(result->_map, 0, sizeof(result->_map));
0541    //
0542    // handle singles first:
0543    //
0544    item_iterator first, last;
0545    set_iterator sfirst, slast;
0546    sfirst = char_set.singles_begin();
0547    slast = char_set.singles_end();
0548    while(sfirst != slast)
0549    {
0550       for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
0551       {
0552          if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
0553             == this->m_traits.translate(sfirst->first, this->m_icase))
0554             result->_map[i] = true;
0555       }
0556       ++sfirst;
0557    }
0558    //
0559    // OK now handle ranges:
0560    //
0561    first = char_set.ranges_begin();
0562    last = char_set.ranges_end();
0563    while(first != last)
0564    {
0565       // first grab the endpoints of the range:
0566       charT c1 = this->m_traits.translate(first->first, this->m_icase);
0567       ++first;
0568       charT c2 = this->m_traits.translate(first->first, this->m_icase);
0569       ++first;
0570       // different actions now depending upon whether collation is turned on:
0571       if(flags() & regex_constants::collate)
0572       {
0573          // we need to transform our range into sort keys:
0574          charT c3[2] = { c1, charT(0), };
0575          string_type s1 = this->m_traits.transform(c3, c3+1);
0576          c3[0] = c2;
0577          string_type s2 = this->m_traits.transform(c3, c3+1);
0578          if(s1 > s2)
0579          {
0580             // Oops error:
0581             return 0;
0582          }
0583          BOOST_REGEX_ASSERT(c3[1] == charT(0));
0584          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
0585          {
0586             c3[0] = static_cast<charT>(i);
0587             string_type s3 = this->m_traits.transform(c3, c3 +1);
0588             if((s1 <= s3) && (s3 <= s2))
0589                result->_map[i] = true;
0590          }
0591       }
0592       else
0593       {
0594          if(char_less(c2, c1))
0595          {
0596             // Oops error:
0597             return 0;
0598          }
0599          // everything in range matches:
0600          std::memset(result->_map + static_cast<unsigned char>(c1), true, static_cast<unsigned char>(1u) + static_cast<unsigned char>(static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1)));
0601       }
0602    }
0603    //
0604    // and now the classes:
0605    //
0606    typedef typename traits::char_class_type m_type;
0607    m_type m = char_set.classes();
0608    if(flags() & regbase::icase)
0609    {
0610       // adjust m as needed:
0611       if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
0612          m |= m_alpha_mask;
0613    }
0614    if(m != 0)
0615    {
0616       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
0617       {
0618          if(this->m_traits.isctype(static_cast<charT>(i), m))
0619             result->_map[i] = true;
0620       }
0621    }
0622    //
0623    // and now the negated classes:
0624    //
0625    m = char_set.negated_classes();
0626    if(flags() & regbase::icase)
0627    {
0628       // adjust m as needed:
0629       if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
0630          m |= m_alpha_mask;
0631    }
0632    if(m != 0)
0633    {
0634       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
0635       {
0636          if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
0637             result->_map[i] = true;
0638       }
0639    }
0640    //
0641    // now process the equivalence classes:
0642    //
0643    sfirst = char_set.equivalents_begin();
0644    slast = char_set.equivalents_end();
0645    while(sfirst != slast)
0646    {
0647       string_type s;
0648       BOOST_REGEX_ASSERT(static_cast<charT>(0) == sfirst->second);
0649       s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
0650       if(s.empty())
0651          return 0;  // invalid or unsupported equivalence class
0652       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
0653       {
0654          charT c[2] = { (static_cast<charT>(i)), charT(0), };
0655          string_type s2 = this->m_traits.transform_primary(c, c+1);
0656          if(s == s2)
0657             result->_map[i] = true;
0658       }
0659       ++sfirst;
0660    }
0661    if(negate)
0662    {
0663       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
0664       {
0665          result->_map[i] = !(result->_map[i]);
0666       }
0667    }
0668    return result;
0669 }
0670
0671 template <class charT, class traits>
0672 void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
0673 {
0674    if(this->m_pdata->m_status)
0675       return;
0676    // we've added all the states we need, now finish things off.
0677    // start by adding a terminating state:
0678    append_state(syntax_element_match);
0679    // extend storage to store original expression:
0680    std::ptrdiff_t len = p2 - p1;
0681    m_pdata->m_expression_len = len;
0682    charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
0683    m_pdata->m_expression = ps;
0684    BOOST_REGEX_DETAIL_NS::copy(p1, p2, ps);
0685    ps[p2 - p1] = 0;
0686    // fill in our other data...
0687    // successful parsing implies a zero status:
0688    m_pdata->m_status = 0;
0689    // get the first state of the machine:
0690    m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
0691    // fixup pointers in the machine:
0692    fixup_pointers(m_pdata->m_first_state);
0693    if(m_has_recursions)
0694    {
0695       m_pdata->m_has_recursions = true;
0696       fixup_recursions(m_pdata->m_first_state);
0697       if(this->m_pdata->m_status)
0698          return;
0699    }
0700    else
0701       m_pdata->m_has_recursions = false;
0702    // create nested startmaps:
0703    create_startmaps(m_pdata->m_first_state);
0704    // create main startmap:
0705    std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
0706    m_pdata->m_can_be_null = 0;
0707
0708    m_bad_repeats = 0;
0709    if(m_has_recursions)
0710       m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
0711    create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
0712    // get the restart type:
0713    m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
0714    // optimise a leading repeat if there is one:
0715    probe_leading_repeat(m_pdata->m_first_state);
0716 }
0717
0718 template <class charT, class traits>
0719 void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
0720 {
0721    while(state)
0722    {
0723       switch(state->type)
0724       {
0725       case syntax_element_recurse:
0726          m_has_recursions = true;
0727          if(state->next.i)
0728             state->next.p = getaddress(state->next.i, state);
0729          else
0730             state->next.p = 0;
0731          break;
0732       case syntax_element_rep:
0733       case syntax_element_dot_rep:
0734       case syntax_element_char_rep:
0735       case syntax_element_short_set_rep:
0736       case syntax_element_long_set_rep:
0737          // set the state_id of this repeat:
0738          static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
0739          BOOST_FALLTHROUGH;
0740       case syntax_element_alt:
0741          std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
0742          static_cast<re_alt*>(state)->can_be_null = 0;
0743          BOOST_FALLTHROUGH;
0744       case syntax_element_jump:
0745          static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
0746          BOOST_FALLTHROUGH;
0747       default:
0748          if(state->next.i)
0749             state->next.p = getaddress(state->next.i, state);
0750          else
0751             state->next.p = 0;
0752       }
0753       state = state->next.p;
0754    }
0755 }
0756
0757 template <class charT, class traits>
0758 void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
0759 {
0760    re_syntax_base* base = state;
0761    while(state)
0762    {
0763       switch(state->type)
0764       {
0765       case syntax_element_assert_backref:
0766          {
0767             // just check that the index is valid:
0768             int idx = static_cast<const re_brace*>(state)->index;
0769             if(idx < 0)
0770             {
0771                idx = -idx-1;
0772                if(idx >= hash_value_mask)
0773                {
0774                   idx = m_pdata->get_id(idx);
0775                   if(idx <= 0)
0776                   {
0777                      // check of sub-expression that doesn't exist:
0778                      if(0 == this->m_pdata->m_status) // update the error code if not already set
0779                         this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
0780                      //
0781                      // clear the expression, we should be empty:
0782                      //
0783                      this->m_pdata->m_expression = 0;
0784                      this->m_pdata->m_expression_len = 0;
0785                      //
0786                      // and throw if required:
0787                      //
0788                      if(0 == (this->flags() & regex_constants::no_except))
0789                      {
0790                         std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
0791                         boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
0792                         e.raise();
0793                      }
0794                   }
0795                }
0796             }
0797          }
0798          break;
0799       case syntax_element_recurse:
0800          {
0801             bool ok = false;
0802             re_syntax_base* p = base;
0803             std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
0804             if(idx >= hash_value_mask)
0805             {
0806                //
0807                // There may be more than one capture group with this hash, just do what Perl
0808                // does and recurse to the leftmost:
0809                //
0810                idx = m_pdata->get_id(static_cast<int>(idx));
0811             }
0812             if(idx < 0)
0813             {
0814                ok = false;
0815             }
0816             else
0817             {
0818                while(p)
0819                {
0820                   if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
0821                   {
0822                      //
0823                      // We've found the target of the recursion, set the jump target:
0824                      //
0825                      static_cast<re_jump*>(state)->alt.p = p;
0826                      ok = true;
0827                      //
0828                      // Now scan the target for nested repeats:
0829                      //
0830                      p = p->next.p;
0831                      int next_rep_id = 0;
0832                      while(p)
0833                      {
0834                         switch(p->type)
0835                         {
0836                         case syntax_element_rep:
0837                         case syntax_element_dot_rep:
0838                         case syntax_element_char_rep:
0839                         case syntax_element_short_set_rep:
0840                         case syntax_element_long_set_rep:
0841                            next_rep_id = static_cast<re_repeat*>(p)->state_id;
0842                            break;
0843                         case syntax_element_endmark:
0844                            if(static_cast<const re_brace*>(p)->index == idx)
0845                               next_rep_id = -1;
0846                            break;
0847                         default:
0848                            break;
0849                         }
0850                         if(next_rep_id)
0851                            break;
0852                         p = p->next.p;
0853                      }
0854                      if(next_rep_id > 0)
0855                      {
0856                         static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
0857                      }
0858
0859                      break;
0860                   }
0861                   p = p->next.p;
0862                }
0863             }
0864             if(!ok)
0865             {
0866                // recursion to sub-expression that doesn't exist:
0867                if(0 == this->m_pdata->m_status) // update the error code if not already set
0868                   this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
0869                //
0870                // clear the expression, we should be empty:
0871                //
0872                this->m_pdata->m_expression = 0;
0873                this->m_pdata->m_expression_len = 0;
0874                //
0875                // and throw if required:
0876                //
0877                if(0 == (this->flags() & regex_constants::no_except))
0878                {
0879                   std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
0880                   boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
0881                   e.raise();
0882                }
0883             }
0884          }
0885          break;
0886       default:
0887          break;
0888       }
0889       state = state->next.p;
0890    }
0891 }
0892
0893 template <class charT, class traits>
0894 void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
0895 {
0896    // non-recursive implementation:
0897    // create the last map in the machine first, so that earlier maps
0898    // can make use of the result...
0899    //
0900    // This was originally a recursive implementation, but that caused stack
0901    // overflows with complex expressions on small stacks (think COM+).
0902
0903    // start by saving the case setting:
0904    bool l_icase = m_icase;
0905    std::vector<std::pair<bool, re_syntax_base*> > v;
0906
0907    while(state)
0908    {
0909       switch(state->type)
0910       {
0911       case syntax_element_toggle_case:
0912          // we need to track case changes here:
0913          m_icase = static_cast<re_case*>(state)->icase;
0914          state = state->next.p;
0915          continue;
0916       case syntax_element_alt:
0917       case syntax_element_rep:
0918       case syntax_element_dot_rep:
0919       case syntax_element_char_rep:
0920       case syntax_element_short_set_rep:
0921       case syntax_element_long_set_rep:
0922          // just push the state onto our stack for now:
0923          v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
0924          state = state->next.p;
0925          break;
0926       case syntax_element_backstep:
0927          // we need to calculate how big the backstep is:
0928          static_cast<re_brace*>(state)->index
0929             = this->calculate_backstep(state->next.p);
0930          if(static_cast<re_brace*>(state)->index < 0)
0931          {
0932             // Oops error:
0933             if(0 == this->m_pdata->m_status) // update the error code if not already set
0934                this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
0935             //
0936             // clear the expression, we should be empty:
0937             //
0938             this->m_pdata->m_expression = 0;
0939             this->m_pdata->m_expression_len = 0;
0940             //
0941             // and throw if required:
0942             //
0943             if(0 == (this->flags() & regex_constants::no_except))
0944             {
0945                std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
0946                boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
0947                e.raise();
0948             }
0949          }
0950          BOOST_FALLTHROUGH;
0951       default:
0952          state = state->next.p;
0953       }
0954    }
0955
0956    // now work through our list, building all the maps as we go:
0957    while(!v.empty())
0958    {
0959       // Initialize m_recursion_checks if we need it:
0960       if(m_has_recursions)
0961          m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
0962
0963       const std::pair<bool, re_syntax_base*>& p = v.back();
0964       m_icase = p.first;
0965       state = p.second;
0966       v.pop_back();
0967
0968       // Build maps:
0969       m_bad_repeats = 0;
0970       create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
0971       m_bad_repeats = 0;
0972
0973       if(m_has_recursions)
0974          m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
0975       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);
0976       // adjust the type of the state to allow for faster matching:
0977       state->type = this->get_repeat_type(state);
0978    }
0979    // restore case sensitivity:
0980    m_icase = l_icase;
0981 }
0982
0983 template <class charT, class traits>
0984 int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
0985 {
0986    typedef typename traits::char_class_type m_type;
0987    int result = 0;
0988    while(state)
0989    {
0990       switch(state->type)
0991       {
0992       case syntax_element_startmark:
0993          if((static_cast<re_brace*>(state)->index == -1)
0994             || (static_cast<re_brace*>(state)->index == -2))
0995          {
0996             state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
0997             continue;
0998          }
0999          else if(static_cast<re_brace*>(state)->index == -3)
1000          {
1001             state = state->next.p->next.p;
1002             continue;
1003          }
1004          break;
1005       case syntax_element_endmark:
1006          if((static_cast<re_brace*>(state)->index == -1)
1007             || (static_cast<re_brace*>(state)->index == -2))
1008             return result;
1009          break;
1010       case syntax_element_literal:
1011          result += static_cast<re_literal*>(state)->length;
1012          break;
1013       case syntax_element_wild:
1014       case syntax_element_set:
1015          result += 1;
1016          break;
1017       case syntax_element_dot_rep:
1018       case syntax_element_char_rep:
1019       case syntax_element_short_set_rep:
1020       case syntax_element_backref:
1021       case syntax_element_rep:
1022       case syntax_element_combining:
1023       case syntax_element_long_set_rep:
1024       case syntax_element_backstep:
1025          {
1026             re_repeat* rep = static_cast<re_repeat *>(state);
1027             // adjust the type of the state to allow for faster matching:
1028             state->type = this->get_repeat_type(state);
1029             if((state->type == syntax_element_dot_rep)
1030                || (state->type == syntax_element_char_rep)
1031                || (state->type == syntax_element_short_set_rep))
1032             {
1033                if(rep->max != rep->min)
1034                   return -1;
1035                result += static_cast<int>(rep->min);
1036                state = rep->alt.p;
1037                continue;
1038             }
1039             else if(state->type == syntax_element_long_set_rep)
1040             {
1041                BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_long_set);
1042                if(static_cast<re_set_long<m_type>*>(rep->next.p)->singleton == 0)
1043                   return -1;
1044                if(rep->max != rep->min)
1045                   return -1;
1046                result += static_cast<int>(rep->min);
1047                state = rep->alt.p;
1048                continue;
1049             }
1050          }
1051          return -1;
1052       case syntax_element_long_set:
1053          if(static_cast<re_set_long<m_type>*>(state)->singleton == 0)
1054             return -1;
1055          result += 1;
1056          break;
1057       case syntax_element_jump:
1058          state = static_cast<re_jump*>(state)->alt.p;
1059          continue;
1060       case syntax_element_alt:
1061          {
1062             int r1 = calculate_backstep(state->next.p);
1063             int r2 = calculate_backstep(static_cast<re_alt*>(state)->alt.p);
1064             if((r1 < 0) || (r1 != r2))
1065                return -1;
1066             return result + r1;
1067          }
1068       default:
1069          break;
1070       }
1071       state = state->next.p;
1072    }
1073    return -1;
1074 }
1075
1076 struct recursion_saver
1077 {
1078    std::vector<unsigned char> saved_state;
1079    std::vector<unsigned char>* state;
1080    recursion_saver(std::vector<unsigned char>* p) : saved_state(*p), state(p) {}
1081    ~recursion_saver()
1082    {
1083       state->swap(saved_state);
1084    }
1085 };
1086
1087 template <class charT, class traits>
1088 void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
1089 {
1090    recursion_saver saved_recursions(&m_recursion_checks);
1091    int not_last_jump = 1;
1092    re_syntax_base* recursion_start = 0;
1093    int recursion_sub = 0;
1094    re_syntax_base* recursion_restart = 0;
1095
1096    // track case sensitivity:
1097    bool l_icase = m_icase;
1098
1099    while(state)
1100    {
1101       switch(state->type)
1102       {
1103       case syntax_element_toggle_case:
1104          l_icase = static_cast<re_case*>(state)->icase;
1105          state = state->next.p;
1106          break;
1107       case syntax_element_literal:
1108       {
1109          // don't set anything in *pnull, set each element in l_map
1110          // that could match the first character in the literal:
1111          if(l_map)
1112          {
1113             l_map[0] |= mask_init;
1114             charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
1115             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1116             {
1117                if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
1118                   l_map[i] |= mask;
1119             }
1120          }
1121          return;
1122       }
1123       case syntax_element_end_line:
1124       {
1125          // next character must be a line separator (if there is one):
1126          if(l_map)
1127          {
1128             l_map[0] |= mask_init;
1129             l_map[static_cast<unsigned>('\n')] |= mask;
1130             l_map[static_cast<unsigned>('\r')] |= mask;
1131             l_map[static_cast<unsigned>('\f')] |= mask;
1132             l_map[0x85] |= mask;
1133          }
1134          // now figure out if we can match a NULL string at this point:
1135          if(pnull)
1136             create_startmap(state->next.p, 0, pnull, mask);
1137          return;
1138       }
1139       case syntax_element_recurse:
1140          {
1141             BOOST_REGEX_ASSERT(static_cast<const re_jump*>(state)->alt.p->type == syntax_element_startmark);
1142             recursion_sub = static_cast<re_brace*>(static_cast<const re_jump*>(state)->alt.p)->index;
1143             if(m_recursion_checks[recursion_sub] & 1u)
1144             {
1145                // Infinite recursion!!
1146                if(0 == this->m_pdata->m_status) // update the error code if not already set
1147                   this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
1148                //
1149                // clear the expression, we should be empty:
1150                //
1151                this->m_pdata->m_expression = 0;
1152                this->m_pdata->m_expression_len = 0;
1153                //
1154                // and throw if required:
1155                //
1156                if(0 == (this->flags() & regex_constants::no_except))
1157                {
1158                   std::string message = "Encountered an infinite recursion.";
1159                   boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
1160                   e.raise();
1161                }
1162             }
1163             else if(recursion_start == 0)
1164             {
1165                recursion_start = state;
1166                recursion_restart = state->next.p;
1167                state = static_cast<re_jump*>(state)->alt.p;
1168                m_recursion_checks[recursion_sub] |= 1u;
1169                break;
1170             }
1171             m_recursion_checks[recursion_sub] |= 1u;
1172             // can't handle nested recursion here...
1173             BOOST_FALLTHROUGH;
1174          }
1175       case syntax_element_backref:
1176          // can be null, and any character can match:
1177          if(pnull)
1178             *pnull |= mask;
1179          BOOST_FALLTHROUGH;
1180       case syntax_element_wild:
1181       {
1182          // can't be null, any character can match:
1183          set_all_masks(l_map, mask);
1184          return;
1185       }
1186       case syntax_element_accept:
1187       case syntax_element_match:
1188       {
1189          // must be null, any character can match:
1190          set_all_masks(l_map, mask);
1191          if(pnull)
1192             *pnull |= mask;
1193          return;
1194       }
1195       case syntax_element_word_start:
1196       {
1197          // recurse, then AND with all the word characters:
1198          create_startmap(state->next.p, l_map, pnull, mask);
1199          if(l_map)
1200          {
1201             l_map[0] |= mask_init;
1202             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1203             {
1204                if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
1205                   l_map[i] &= static_cast<unsigned char>(~mask);
1206             }
1207          }
1208          return;
1209       }
1210       case syntax_element_word_end:
1211       {
1212          // recurse, then AND with all the word characters:
1213          create_startmap(state->next.p, l_map, pnull, mask);
1214          if(l_map)
1215          {
1216             l_map[0] |= mask_init;
1217             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1218             {
1219                if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
1220                   l_map[i] &= static_cast<unsigned char>(~mask);
1221             }
1222          }
1223          return;
1224       }
1225       case syntax_element_buffer_end:
1226       {
1227          // we *must be null* :
1228          if(pnull)
1229             *pnull |= mask;
1230          return;
1231       }
1232       case syntax_element_long_set:
1233          if(l_map)
1234          {
1235             typedef typename traits::char_class_type m_type;
1236             if(static_cast<re_set_long<m_type>*>(state)->singleton)
1237             {
1238                l_map[0] |= mask_init;
1239                for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1240                {
1241                   charT c = static_cast<charT>(i);
1242                   if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<m_type>*>(state), *m_pdata, l_icase))
1243                      l_map[i] |= mask;
1244                }
1245             }
1246             else
1247                set_all_masks(l_map, mask);
1248          }
1249          return;
1250       case syntax_element_set:
1251          if(l_map)
1252          {
1253             l_map[0] |= mask_init;
1254             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1255             {
1256                if(static_cast<re_set*>(state)->_map[
1257                   static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1258                   l_map[i] |= mask;
1259             }
1260          }
1261          return;
1262       case syntax_element_jump:
1263          // take the jump:
1264          state = static_cast<re_alt*>(state)->alt.p;
1265          not_last_jump = -1;
1266          break;
1267       case syntax_element_alt:
1268       case syntax_element_rep:
1269       case syntax_element_dot_rep:
1270       case syntax_element_char_rep:
1271       case syntax_element_short_set_rep:
1272       case syntax_element_long_set_rep:
1273          {
1274             re_alt* rep = static_cast<re_alt*>(state);
1275             if(rep->_map[0] & mask_init)
1276             {
1277                if(l_map)
1278                {
1279                   // copy previous results:
1280                   l_map[0] |= mask_init;
1281                   for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1282                   {
1283                      if(rep->_map[i] & mask_any)
1284                         l_map[i] |= mask;
1285                   }
1286                }
1287                if(pnull)
1288                {
1289                   if(rep->can_be_null & mask_any)
1290                      *pnull |= mask;
1291                }
1292             }
1293             else
1294             {
1295                // we haven't created a startmap for this alternative yet
1296                // so take the union of the two options:
1297                if(is_bad_repeat(state))
1298                {
1299                   set_all_masks(l_map, mask);
1300                   if(pnull)
1301                      *pnull |= mask;
1302                   return;
1303                }
1304                set_bad_repeat(state);
1305                create_startmap(state->next.p, l_map, pnull, mask);
1306                if((state->type == syntax_element_alt)
1307                   || (static_cast<re_repeat*>(state)->min == 0)
1308                   || (not_last_jump == 0))
1309                   create_startmap(rep->alt.p, l_map, pnull, mask);
1310             }
1311          }
1312          return;
1313       case syntax_element_soft_buffer_end:
1314          // match newline or null:
1315          if(l_map)
1316          {
1317             l_map[0] |= mask_init;
1318             l_map[static_cast<unsigned>('\n')] |= mask;
1319             l_map[static_cast<unsigned>('\r')] |= mask;
1320          }
1321          if(pnull)
1322             *pnull |= mask;
1323          return;
1324       case syntax_element_endmark:
1325          // need to handle independent subs as a special case:
1326          if(static_cast<re_brace*>(state)->index < 0)
1327          {
1328             // can be null, any character can match:
1329             set_all_masks(l_map, mask);
1330             if(pnull)
1331                *pnull |= mask;
1332             return;
1333          }
1334          else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
1335          {
1336             // recursion termination:
1337             recursion_start = 0;
1338             state = recursion_restart;
1339             break;
1340          }
1341
1342          //
1343          // Normally we just go to the next state... but if this sub-expression is
1344          // the target of a recursion, then we might be ending a recursion, in which
1345          // case we should check whatever follows that recursion, as well as whatever
1346          // follows this state:
1347          //
1348          if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
1349          {
1350             bool ok = false;
1351             re_syntax_base* p = m_pdata->m_first_state;
1352             while(p)
1353             {
1354                if(p->type == syntax_element_recurse)
1355                {
1356                   re_brace* p2 = static_cast<re_brace*>(static_cast<re_jump*>(p)->alt.p);
1357                   if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
1358                   {
1359                      ok = true;
1360                      break;
1361                   }
1362                }
1363                p = p->next.p;
1364             }
1365             if(ok && ((m_recursion_checks[static_cast<re_brace*>(state)->index] & 2u) == 0))
1366             {
1367                m_recursion_checks[static_cast<re_brace*>(state)->index] |= 2u;
1368                create_startmap(p->next.p, l_map, pnull, mask);
1369             }
1370          }
1371          state = state->next.p;
1372          break;
1373
1374       case syntax_element_commit:
1375          set_all_masks(l_map, mask);
1376          // Continue scanning so we can figure out whether we can be null:
1377          state = state->next.p;
1378          break;
1379       case syntax_element_startmark:
1380          // need to handle independent subs as a special case:
1381          if(static_cast<re_brace*>(state)->index == -3)
1382          {
1383             state = state->next.p->next.p;
1384             break;
1385          }
1386          BOOST_FALLTHROUGH;
1387       default:
1388          state = state->next.p;
1389       }
1390       ++not_last_jump;
1391    }
1392 }
1393
1394 template <class charT, class traits>
1395 unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1396 {
1397    //
1398    // find out how the machine starts, so we can optimise the search:
1399    //
1400    while(state)
1401    {
1402       switch(state->type)
1403       {
1404       case syntax_element_startmark:
1405       case syntax_element_endmark:
1406          state = state->next.p;
1407          continue;
1408       case syntax_element_start_line:
1409          return regbase::restart_line;
1410       case syntax_element_word_start:
1411          return regbase::restart_word;
1412       case syntax_element_buffer_start:
1413          return regbase::restart_buf;
1414       case syntax_element_restart_continue:
1415          return regbase::restart_continue;
1416       default:
1417          state = 0;
1418          continue;
1419       }
1420    }
1421    return regbase::restart_any;
1422 }
1423
1424 template <class charT, class traits>
1425 void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1426 {
1427    //
1428    // set mask in all of bits elements,
1429    // if bits[0] has mask_init not set then we can
1430    // optimise this to a call to memset:
1431    //
1432    if(bits)
1433    {
1434       if(bits[0] == 0)
1435          (std::memset)(bits, mask, 1u << CHAR_BIT);
1436       else
1437       {
1438          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1439             bits[i] |= mask;
1440       }
1441       bits[0] |= mask_init;
1442    }
1443 }
1444
1445 template <class charT, class traits>
1446 bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1447 {
1448    switch(pt->type)
1449    {
1450    case syntax_element_rep:
1451    case syntax_element_dot_rep:
1452    case syntax_element_char_rep:
1453    case syntax_element_short_set_rep:
1454    case syntax_element_long_set_rep:
1455       {
1456          unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1457          if(state_id >= sizeof(m_bad_repeats) * CHAR_BIT)
1458             return true;  // run out of bits, assume we can't traverse this one.
1459          static const boost::uintmax_t one = 1uL;
1460          return m_bad_repeats & (one << state_id);
1461       }
1462    default:
1463       return false;
1464    }
1465 }
1466
1467 template <class charT, class traits>
1468 void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1469 {
1470    switch(pt->type)
1471    {
1472    case syntax_element_rep:
1473    case syntax_element_dot_rep:
1474    case syntax_element_char_rep:
1475    case syntax_element_short_set_rep:
1476    case syntax_element_long_set_rep:
1477       {
1478          unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1479          static const boost::uintmax_t one = 1uL;
1480          if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
1481             m_bad_repeats |= (one << state_id);
1482       }
1483       break;
1484    default:
1485       break;
1486    }
1487 }
1488
1489 template <class charT, class traits>
1490 syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1491 {
1492    typedef typename traits::char_class_type m_type;
1493    if(state->type == syntax_element_rep)
1494    {
1495       // check to see if we are repeating a single state:
1496       if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1497       {
1498          switch(state->next.p->type)
1499          {
1500          case BOOST_REGEX_DETAIL_NS::syntax_element_wild:
1501             return BOOST_REGEX_DETAIL_NS::syntax_element_dot_rep;
1502          case BOOST_REGEX_DETAIL_NS::syntax_element_literal:
1503             return BOOST_REGEX_DETAIL_NS::syntax_element_char_rep;
1504          case BOOST_REGEX_DETAIL_NS::syntax_element_set:
1505             return BOOST_REGEX_DETAIL_NS::syntax_element_short_set_rep;
1506          case BOOST_REGEX_DETAIL_NS::syntax_element_long_set:
1507             if(static_cast<BOOST_REGEX_DETAIL_NS::re_set_long<m_type>*>(state->next.p)->singleton)
1508                return BOOST_REGEX_DETAIL_NS::syntax_element_long_set_rep;
1509             break;
1510          default:
1511             break;
1512          }
1513       }
1514    }
1515    return state->type;
1516 }
1517
1518 template <class charT, class traits>
1519 void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1520 {
1521    // enumerate our states, and see if we have a leading repeat
1522    // for which failed search restarts can be optimized;
1523    do
1524    {
1525       switch(state->type)
1526       {
1527       case syntax_element_startmark:
1528          if(static_cast<re_brace*>(state)->index >= 0)
1529          {
1530             state = state->next.p;
1531             continue;
1532          }
1533 #ifdef BOOST_MSVC
1534 #  pragma warning(push)
1535 #pragma warning(disable:6011)
1536 #endif
1537          if((static_cast<re_brace*>(state)->index == -1)
1538             || (static_cast<re_brace*>(state)->index == -2))
1539          {
1540             // skip past the zero width assertion:
1541             state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
1542             continue;
1543          }
1544 #ifdef BOOST_MSVC
1545 #  pragma warning(pop)
1546 #endif
1547          if(static_cast<re_brace*>(state)->index == -3)
1548          {
1549             // Have to skip the leading jump state:
1550             state = state->next.p->next.p;
1551             continue;
1552          }
1553          return;
1554       case syntax_element_endmark:
1555       case syntax_element_start_line:
1556       case syntax_element_end_line:
1557       case syntax_element_word_boundary:
1558       case syntax_element_within_word:
1559       case syntax_element_word_start:
1560       case syntax_element_word_end:
1561       case syntax_element_buffer_start:
1562       case syntax_element_buffer_end:
1563       case syntax_element_restart_continue:
1564          state = state->next.p;
1565          break;
1566       case syntax_element_dot_rep:
1567       case syntax_element_char_rep:
1568       case syntax_element_short_set_rep:
1569       case syntax_element_long_set_rep:
1570          if(this->m_has_backrefs == 0)
1571             static_cast<re_repeat*>(state)->leading = true;
1572          BOOST_FALLTHROUGH;
1573       default:
1574          return;
1575       }
1576    }while(state);
1577 }
1578
1579 } // namespace BOOST_REGEX_DETAIL_NS
1580
1581 } // namespace boost
1582
1583 #ifdef BOOST_MSVC
1584 #  pragma warning(pop)
1585 #endif
1586
1587 #ifdef BOOST_MSVC
1588 #pragma warning(push)
1589 #pragma warning(disable: 4103)
1590 #endif
1591 #ifdef BOOST_HAS_ABI_HEADERS
1592 #  include BOOST_ABI_SUFFIX
1593 #endif
1594 #ifdef BOOST_MSVC
1595 #pragma warning(pop)
1596 #endif
1597
1598 #endif