ceph/src/boost/boost/regex/v4/basic_regex_creator.hpp

   1 /*
   2  *
   3  * Copyright (c) 2004
   4  * John Maddock
   5  *
   6  * Use, modification and distribution are subject to the
   7  * Boost Software License, Version 1.0. (See accompanying file
   8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9  *
  10  */
  11
  12  /*
  13   *   LOCATION:    see http://www.boost.org for most recent version.
  14   *   FILE         basic_regex_creator.cpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Declares template class basic_regex_creator which fills in
  17   *                the data members of a regex_data object.
  18   */
  19
  20 #ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
  21 #define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
  22
  23 #ifdef BOOST_MSVC
  24 #pragma warning(push)
  25 #pragma warning(disable: 4103)
  26 #endif
  27 #ifdef BOOST_HAS_ABI_HEADERS
  28 #  include BOOST_ABI_PREFIX
  29 #endif
  30 #ifdef BOOST_MSVC
  31 #pragma warning(pop)
  32 #endif
  33
  34 #ifdef BOOST_MSVC
  35 #  pragma warning(push)
  36 #  pragma warning(disable: 4800)
  37 #endif
  38
  39 namespace boost{
  40
  41 namespace BOOST_REGEX_DETAIL_NS{
  42
  43 template <class charT>
  44 struct digraph : public std::pair<charT, charT>
  45 {
  46    digraph() : std::pair<charT, charT>(charT(0), charT(0)){}
  47    digraph(charT c1) : std::pair<charT, charT>(c1, charT(0)){}
  48    digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
  49    {}
  50    digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
  51    template <class Seq>
  52    digraph(const Seq& s) : std::pair<charT, charT>()
  53    {
  54       BOOST_ASSERT(s.size() <= 2);
  55       BOOST_ASSERT(s.size());
  56       this->first = s[0];
  57       this->second = (s.size() > 1) ? s[1] : 0;
  58    }
  59 };
  60
  61 template <class charT, class traits>
  62 class basic_char_set
  63 {
  64 public:
  65    typedef digraph<charT>                   digraph_type;
  66    typedef typename traits::string_type     string_type;
  67    typedef typename traits::char_class_type m_type;
  68
  69    basic_char_set()
  70    {
  71       m_negate = false;
  72       m_has_digraphs = false;
  73       m_classes = 0;
  74       m_negated_classes = 0;
  75       m_empty = true;
  76    }
  77
  78    void add_single(const digraph_type& s)
  79    {
  80       m_singles.insert(s);
  81       if(s.second)
  82          m_has_digraphs = true;
  83       m_empty = false;
  84    }
  85    void add_range(const digraph_type& first, const digraph_type& end)
  86    {
  87       m_ranges.push_back(first);
  88       m_ranges.push_back(end);
  89       if(first.second)
  90       {
  91          m_has_digraphs = true;
  92          add_single(first);
  93       }
  94       if(end.second)
  95       {
  96          m_has_digraphs = true;
  97          add_single(end);
  98       }
  99       m_empty = false;
 100    }
 101    void add_class(m_type m)
 102    {
 103       m_classes |= m;
 104       m_empty = false;
 105    }
 106    void add_negated_class(m_type m)
 107    {
 108       m_negated_classes |= m;
 109       m_empty = false;
 110    }
 111    void add_equivalent(const digraph_type& s)
 112    {
 113       m_equivalents.insert(s);
 114       if(s.second)
 115       {
 116          m_has_digraphs = true;
 117          add_single(s);
 118       }
 119       m_empty = false;
 120    }
 121    void negate()
 122    {
 123       m_negate = true;
 124       //m_empty = false;
 125    }
 126
 127    //
 128    // accessor functions:
 129    //
 130    bool has_digraphs()const
 131    {
 132       return m_has_digraphs;
 133    }
 134    bool is_negated()const
 135    {
 136       return m_negate;
 137    }
 138    typedef typename std::vector<digraph_type>::const_iterator  list_iterator;
 139    typedef typename std::set<digraph_type>::const_iterator     set_iterator;
 140    set_iterator singles_begin()const
 141    {
 142       return m_singles.begin();
 143    }
 144    set_iterator singles_end()const
 145    {
 146       return m_singles.end();
 147    }
 148    list_iterator ranges_begin()const
 149    {
 150       return m_ranges.begin();
 151    }
 152    list_iterator ranges_end()const
 153    {
 154       return m_ranges.end();
 155    }
 156    set_iterator equivalents_begin()const
 157    {
 158       return m_equivalents.begin();
 159    }
 160    set_iterator equivalents_end()const
 161    {
 162       return m_equivalents.end();
 163    }
 164    m_type classes()const
 165    {
 166       return m_classes;
 167    }
 168    m_type negated_classes()const
 169    {
 170       return m_negated_classes;
 171    }
 172    bool empty()const
 173    {
 174       return m_empty;
 175    }
 176 private:
 177    std::set<digraph_type>    m_singles;         // a list of single characters to match
 178    std::vector<digraph_type> m_ranges;          // a list of end points of our ranges
 179    bool                      m_negate;          // true if the set is to be negated
 180    bool                      m_has_digraphs;    // true if we have digraphs present
 181    m_type                    m_classes;         // character classes to match
 182    m_type                    m_negated_classes; // negated character classes to match
 183    bool                      m_empty;           // whether we've added anything yet
 184    std::set<digraph_type>    m_equivalents;     // a list of equivalence classes
 185 };
 186
 187 template <class charT, class traits>
 188 class basic_regex_creator
 189 {
 190 public:
 191    basic_regex_creator(regex_data<charT, traits>* data);
 192    std::ptrdiff_t getoffset(void* addr)
 193    {
 194       return getoffset(addr, m_pdata->m_data.data());
 195    }
 196    std::ptrdiff_t getoffset(const void* addr, const void* base)
 197    {
 198       return static_cast<const char*>(addr) - static_cast<const char*>(base);
 199    }
 200    re_syntax_base* getaddress(std::ptrdiff_t off)
 201    {
 202       return getaddress(off, m_pdata->m_data.data());
 203    }
 204    re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
 205    {
 206       return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
 207    }
 208    void init(unsigned l_flags)
 209    {
 210       m_pdata->m_flags = l_flags;
 211       m_icase = l_flags & regex_constants::icase;
 212    }
 213    regbase::flag_type flags()
 214    {
 215       return m_pdata->m_flags;
 216    }
 217    void flags(regbase::flag_type f)
 218    {
 219       m_pdata->m_flags = f;
 220       if(m_icase != static_cast<bool>(f & regbase::icase))
 221       {
 222          m_icase = static_cast<bool>(f & regbase::icase);
 223       }
 224    }
 225    re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
 226    re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
 227    re_literal* append_literal(charT c);
 228    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
 229    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
 230    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
 231    void finalize(const charT* p1, const charT* p2);
 232 protected:
 233    regex_data<charT, traits>*    m_pdata;              // pointer to the basic_regex_data struct we are filling in
 234    const ::boost::regex_traits_wrapper<traits>&
 235                                  m_traits;             // convenience reference to traits class
 236    re_syntax_base*               m_last_state;         // the last state we added
 237    bool                          m_icase;              // true for case insensitive matches
 238    unsigned                      m_repeater_id;        // the state_id of the next repeater
 239    bool                          m_has_backrefs;       // true if there are actually any backrefs
 240    unsigned                      m_backrefs;           // bitmask of permitted backrefs
 241    boost::uintmax_t              m_bad_repeats;        // bitmask of repeats we can't deduce a startmap for;
 242    bool                          m_has_recursions;     // set when we have recursive expresisons to fixup
 243    std::vector<unsigned char>    m_recursion_checks;   // notes which recursions we've followed while analysing this expression
 244    typename traits::char_class_type m_word_mask;       // mask used to determine if a character is a word character
 245    typename traits::char_class_type m_mask_space;      // mask used to determine if a character is a word character
 246    typename traits::char_class_type m_lower_mask;       // mask used to determine if a character is a lowercase character
 247    typename traits::char_class_type m_upper_mask;      // mask used to determine if a character is an uppercase character
 248    typename traits::char_class_type m_alpha_mask;      // mask used to determine if a character is an alphabetic character
 249 private:
 250    basic_regex_creator& operator=(const basic_regex_creator&);
 251    basic_regex_creator(const basic_regex_creator&);
 252
 253    void fixup_pointers(re_syntax_base* state);
 254    void fixup_recursions(re_syntax_base* state);
 255    void create_startmaps(re_syntax_base* state);
 256    int calculate_backstep(re_syntax_base* state);
 257    void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
 258    unsigned get_restart_type(re_syntax_base* state);
 259    void set_all_masks(unsigned char* bits, unsigned char);
 260    bool is_bad_repeat(re_syntax_base* pt);
 261    void set_bad_repeat(re_syntax_base* pt);
 262    syntax_element_type get_repeat_type(re_syntax_base* state);
 263    void probe_leading_repeat(re_syntax_base* state);
 264 };
 265
 266 template <class charT, class traits>
 267 basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
 268    : 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)
 269 {
 270    m_pdata->m_data.clear();
 271    m_pdata->m_status = ::boost::regex_constants::error_ok;
 272    static const charT w = 'w';
 273    static const charT s = 's';
 274    static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
 275    static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
 276    static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
 277    m_word_mask = m_traits.lookup_classname(&w, &w +1);
 278    m_mask_space = m_traits.lookup_classname(&s, &s +1);
 279    m_lower_mask = m_traits.lookup_classname(l, l + 5);
 280    m_upper_mask = m_traits.lookup_classname(u, u + 5);
 281    m_alpha_mask = m_traits.lookup_classname(a, a + 5);
 282    m_pdata->m_word_mask = m_word_mask;
 283    BOOST_ASSERT(m_word_mask != 0);
 284    BOOST_ASSERT(m_mask_space != 0);
 285    BOOST_ASSERT(m_lower_mask != 0);
 286    BOOST_ASSERT(m_upper_mask != 0);
 287    BOOST_ASSERT(m_alpha_mask != 0);
 288 }
 289
 290 template <class charT, class traits>
 291 re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
 292 {
 293    // if the state is a backref then make a note of it:
 294    if(t == syntax_element_backref)
 295       this->m_has_backrefs = true;
 296    // append a new state, start by aligning our last one:
 297    m_pdata->m_data.align();
 298    // set the offset to the next state in our last one:
 299    if(m_last_state)
 300       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
 301    // now actually extent our data:
 302    m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
 303    // fill in boilerplate options in the new state:
 304    m_last_state->next.i = 0;
 305    m_last_state->type = t;
 306    return m_last_state;
 307 }
 308
 309 template <class charT, class traits>
 310 re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
 311 {
 312    // append a new state, start by aligning our last one:
 313    m_pdata->m_data.align();
 314    // set the offset to the next state in our last one:
 315    if(m_last_state)
 316       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
 317    // remember the last state position:
 318    std::ptrdiff_t off = getoffset(m_last_state) + s;
 319    // now actually insert our data:
 320    re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
 321    // fill in boilerplate options in the new state:
 322    new_state->next.i = s;
 323    new_state->type = t;
 324    m_last_state = getaddress(off);
 325    return new_state;
 326 }
 327
 328 template <class charT, class traits>
 329 re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
 330 {
 331    re_literal* result;
 332    // start by seeing if we have an existing re_literal we can extend:
 333    if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
 334    {
 335       // no existing re_literal, create a new one:
 336       result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
 337       result->length = 1;
 338       *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
 339    }
 340    else
 341    {
 342       // we have an existing re_literal, extend it:
 343       std::ptrdiff_t off = getoffset(m_last_state);
 344       m_pdata->m_data.extend(sizeof(charT));
 345       m_last_state = result = static_cast<re_literal*>(getaddress(off));
 346       charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
 347       characters[result->length] = m_traits.translate(c, m_icase);
 348       result->length += 1;
 349    }
 350    return result;
 351 }
 352
 353 template <class charT, class traits>
 354 inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
 355    const basic_char_set<charT, traits>& char_set)
 356 {
 357    typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
 358    return char_set.has_digraphs()
 359       ? append_set(char_set, static_cast<mpl::false_*>(0))
 360       : append_set(char_set, static_cast<truth_type*>(0));
 361 }
 362
 363 template <class charT, class traits>
 364 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
 365    const basic_char_set<charT, traits>& char_set, mpl::false_*)
 366 {
 367    typedef typename traits::string_type string_type;
 368    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
 369    typedef typename basic_char_set<charT, traits>::set_iterator  set_iterator;
 370    typedef typename traits::char_class_type m_type;
 371
 372    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>)));
 373    //
 374    // fill in the basics:
 375    //
 376    result->csingles = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.singles_begin(), char_set.singles_end()));
 377    result->cranges = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
 378    result->cequivalents = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
 379    result->cclasses = char_set.classes();
 380    result->cnclasses = char_set.negated_classes();
 381    if(flags() & regbase::icase)
 382    {
 383       // adjust classes as needed:
 384       if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
 385          result->cclasses |= m_alpha_mask;
 386       if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
 387          result->cnclasses |= m_alpha_mask;
 388    }
 389
 390    result->isnot = char_set.is_negated();
 391    result->singleton = !char_set.has_digraphs();
 392    //
 393    // remember where the state is for later:
 394    //
 395    std::ptrdiff_t offset = getoffset(result);
 396    //
 397    // now extend with all the singles:
 398    //
 399    item_iterator first, last;
 400    set_iterator sfirst, slast;
 401    sfirst = char_set.singles_begin();
 402    slast = char_set.singles_end();
 403    while(sfirst != slast)
 404    {
 405       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (sfirst->first == static_cast<charT>(0) ? 1 : sfirst->second ? 3 : 2)));
 406       p[0] = m_traits.translate(sfirst->first, m_icase);
 407       if(sfirst->first == static_cast<charT>(0))
 408       {
 409          p[0] = 0;
 410       }
 411       else if(sfirst->second)
 412       {
 413          p[1] = m_traits.translate(sfirst->second, m_icase);
 414          p[2] = 0;
 415       }
 416       else
 417          p[1] = 0;
 418       ++sfirst;
 419    }
 420    //
 421    // now extend with all the ranges:
 422    //
 423    first = char_set.ranges_begin();
 424    last = char_set.ranges_end();
 425    while(first != last)
 426    {
 427       // first grab the endpoints of the range:
 428       digraph<charT> c1 = *first;
 429       c1.first = this->m_traits.translate(c1.first, this->m_icase);
 430       c1.second = this->m_traits.translate(c1.second, this->m_icase);
 431       ++first;
 432       digraph<charT> c2 = *first;
 433       c2.first = this->m_traits.translate(c2.first, this->m_icase);
 434       c2.second = this->m_traits.translate(c2.second, this->m_icase);
 435       ++first;
 436       string_type s1, s2;
 437       // different actions now depending upon whether collation is turned on:
 438       if(flags() & regex_constants::collate)
 439       {
 440          // we need to transform our range into sort keys:
 441          charT a1[3] = { c1.first, c1.second, charT(0), };
 442          charT a2[3] = { c2.first, c2.second, charT(0), };
 443          s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
 444          s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
 445          if(s1.size() == 0)
 446             s1 = string_type(1, charT(0));
 447          if(s2.size() == 0)
 448             s2 = string_type(1, charT(0));
 449       }
 450       else
 451       {
 452          if(c1.second)
 453          {
 454             s1.insert(s1.end(), c1.first);
 455             s1.insert(s1.end(), c1.second);
 456          }
 457          else
 458             s1 = string_type(1, c1.first);
 459          if(c2.second)
 460          {
 461             s2.insert(s2.end(), c2.first);
 462             s2.insert(s2.end(), c2.second);
 463          }
 464          else
 465             s2.insert(s2.end(), c2.first);
 466       }
 467       if(s1 > s2)
 468       {
 469          // Oops error:
 470          return 0;
 471       }
 472       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
 473       BOOST_REGEX_DETAIL_NS::copy(s1.begin(), s1.end(), p);
 474       p[s1.size()] = charT(0);
 475       p += s1.size() + 1;
 476       BOOST_REGEX_DETAIL_NS::copy(s2.begin(), s2.end(), p);
 477       p[s2.size()] = charT(0);
 478    }
 479    //
 480    // now process the equivalence classes:
 481    //
 482    sfirst = char_set.equivalents_begin();
 483    slast = char_set.equivalents_end();
 484    while(sfirst != slast)
 485    {
 486       string_type s;
 487       if(sfirst->second)
 488       {
 489          charT cs[3] = { sfirst->first, sfirst->second, charT(0), };
 490          s = m_traits.transform_primary(cs, cs+2);
 491       }
 492       else
 493          s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
 494       if(s.empty())
 495          return 0;  // invalid or unsupported equivalence class
 496       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
 497       BOOST_REGEX_DETAIL_NS::copy(s.begin(), s.end(), p);
 498       p[s.size()] = charT(0);
 499       ++sfirst;
 500    }
 501    //
 502    // finally reset the address of our last state:
 503    //
 504    m_last_state = result = static_cast<re_set_long<m_type>*>(getaddress(offset));
 505    return result;
 506 }
 507
 508 template<class T>
 509 inline bool char_less(T t1, T t2)
 510 {
 511    return t1 < t2;
 512 }
 513 inline bool char_less(char t1, char t2)
 514 {
 515    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
 516 }
 517 inline bool char_less(signed char t1, signed char t2)
 518 {
 519    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
 520 }
 521
 522 template <class charT, class traits>
 523 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
 524    const basic_char_set<charT, traits>& char_set, mpl::true_*)
 525 {
 526    typedef typename traits::string_type string_type;
 527    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
 528    typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
 529
 530    re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
 531    bool negate = char_set.is_negated();
 532    std::memset(result->_map, 0, sizeof(result->_map));
 533    //
 534    // handle singles first:
 535    //
 536    item_iterator first, last;
 537    set_iterator sfirst, slast;
 538    sfirst = char_set.singles_begin();
 539    slast = char_set.singles_end();
 540    while(sfirst != slast)
 541    {
 542       for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
 543       {
 544          if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
 545             == this->m_traits.translate(sfirst->first, this->m_icase))
 546             result->_map[i] = true;
 547       }
 548       ++sfirst;
 549    }
 550    //
 551    // OK now handle ranges:
 552    //
 553    first = char_set.ranges_begin();
 554    last = char_set.ranges_end();
 555    while(first != last)
 556    {
 557       // first grab the endpoints of the range:
 558       charT c1 = this->m_traits.translate(first->first, this->m_icase);
 559       ++first;
 560       charT c2 = this->m_traits.translate(first->first, this->m_icase);
 561       ++first;
 562       // different actions now depending upon whether collation is turned on:
 563       if(flags() & regex_constants::collate)
 564       {
 565          // we need to transform our range into sort keys:
 566          charT c3[2] = { c1, charT(0), };
 567          string_type s1 = this->m_traits.transform(c3, c3+1);
 568          c3[0] = c2;
 569          string_type s2 = this->m_traits.transform(c3, c3+1);
 570          if(s1 > s2)
 571          {
 572             // Oops error:
 573             return 0;
 574          }
 575          BOOST_ASSERT(c3[1] == charT(0));
 576          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
 577          {
 578             c3[0] = static_cast<charT>(i);
 579             string_type s3 = this->m_traits.transform(c3, c3 +1);
 580             if((s1 <= s3) && (s3 <= s2))
 581                result->_map[i] = true;
 582          }
 583       }
 584       else
 585       {
 586          if(char_less(c2, c1))
 587          {
 588             // Oops error:
 589             return 0;
 590          }
 591          // everything in range matches:
 592          std::memset(result->_map + static_cast<unsigned char>(c1), true, 1 + static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1));
 593       }
 594    }
 595    //
 596    // and now the classes:
 597    //
 598    typedef typename traits::char_class_type m_type;
 599    m_type m = char_set.classes();
 600    if(flags() & regbase::icase)
 601    {
 602       // adjust m as needed:
 603       if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
 604          m |= m_alpha_mask;
 605    }
 606    if(m != 0)
 607    {
 608       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
 609       {
 610          if(this->m_traits.isctype(static_cast<charT>(i), m))
 611             result->_map[i] = true;
 612       }
 613    }
 614    //
 615    // and now the negated classes:
 616    //
 617    m = char_set.negated_classes();
 618    if(flags() & regbase::icase)
 619    {
 620       // adjust m as needed:
 621       if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
 622          m |= m_alpha_mask;
 623    }
 624    if(m != 0)
 625    {
 626       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
 627       {
 628          if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
 629             result->_map[i] = true;
 630       }
 631    }
 632    //
 633    // now process the equivalence classes:
 634    //
 635    sfirst = char_set.equivalents_begin();
 636    slast = char_set.equivalents_end();
 637    while(sfirst != slast)
 638    {
 639       string_type s;
 640       BOOST_ASSERT(static_cast<charT>(0) == sfirst->second);
 641       s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
 642       if(s.empty())
 643          return 0;  // invalid or unsupported equivalence class
 644       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
 645       {
 646          charT c[2] = { (static_cast<charT>(i)), charT(0), };
 647          string_type s2 = this->m_traits.transform_primary(c, c+1);
 648          if(s == s2)
 649             result->_map[i] = true;
 650       }
 651       ++sfirst;
 652    }
 653    if(negate)
 654    {
 655       for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
 656       {
 657          result->_map[i] = !(result->_map[i]);
 658       }
 659    }
 660    return result;
 661 }
 662
 663 template <class charT, class traits>
 664 void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
 665 {
 666    if(this->m_pdata->m_status)
 667       return;
 668    // we've added all the states we need, now finish things off.
 669    // start by adding a terminating state:
 670    append_state(syntax_element_match);
 671    // extend storage to store original expression:
 672    std::ptrdiff_t len = p2 - p1;
 673    m_pdata->m_expression_len = len;
 674    charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
 675    m_pdata->m_expression = ps;
 676    BOOST_REGEX_DETAIL_NS::copy(p1, p2, ps);
 677    ps[p2 - p1] = 0;
 678    // fill in our other data...
 679    // successful parsing implies a zero status:
 680    m_pdata->m_status = 0;
 681    // get the first state of the machine:
 682    m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
 683    // fixup pointers in the machine:
 684    fixup_pointers(m_pdata->m_first_state);
 685    if(m_has_recursions)
 686    {
 687       m_pdata->m_has_recursions = true;
 688       fixup_recursions(m_pdata->m_first_state);
 689       if(this->m_pdata->m_status)
 690          return;
 691    }
 692    else
 693       m_pdata->m_has_recursions = false;
 694    // create nested startmaps:
 695    create_startmaps(m_pdata->m_first_state);
 696    // create main startmap:
 697    std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
 698    m_pdata->m_can_be_null = 0;
 699
 700    m_bad_repeats = 0;
 701    if(m_has_recursions)
 702       m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
 703    create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
 704    // get the restart type:
 705    m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
 706    // optimise a leading repeat if there is one:
 707    probe_leading_repeat(m_pdata->m_first_state);
 708 }
 709
 710 template <class charT, class traits>
 711 void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
 712 {
 713    while(state)
 714    {
 715       switch(state->type)
 716       {
 717       case syntax_element_recurse:
 718          m_has_recursions = true;
 719          if(state->next.i)
 720             state->next.p = getaddress(state->next.i, state);
 721          else
 722             state->next.p = 0;
 723          break;
 724       case syntax_element_rep:
 725       case syntax_element_dot_rep:
 726       case syntax_element_char_rep:
 727       case syntax_element_short_set_rep:
 728       case syntax_element_long_set_rep:
 729          // set the state_id of this repeat:
 730          static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
 731          BOOST_FALLTHROUGH;
 732       case syntax_element_alt:
 733          std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
 734          static_cast<re_alt*>(state)->can_be_null = 0;
 735          BOOST_FALLTHROUGH;
 736       case syntax_element_jump:
 737          static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
 738          BOOST_FALLTHROUGH;
 739       default:
 740          if(state->next.i)
 741             state->next.p = getaddress(state->next.i, state);
 742          else
 743             state->next.p = 0;
 744       }
 745       state = state->next.p;
 746    }
 747 }
 748
 749 template <class charT, class traits>
 750 void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
 751 {
 752    re_syntax_base* base = state;
 753    while(state)
 754    {
 755       switch(state->type)
 756       {
 757       case syntax_element_assert_backref:
 758          {
 759             // just check that the index is valid:
 760             int idx = static_cast<const re_brace*>(state)->index;
 761             if(idx < 0)
 762             {
 763                idx = -idx-1;
 764                if(idx >= 10000)
 765                {
 766                   idx = m_pdata->get_id(idx);
 767                   if(idx <= 0)
 768                   {
 769                      // check of sub-expression that doesn't exist:
 770                      if(0 == this->m_pdata->m_status) // update the error code if not already set
 771                         this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
 772                      //
 773                      // clear the expression, we should be empty:
 774                      //
 775                      this->m_pdata->m_expression = 0;
 776                      this->m_pdata->m_expression_len = 0;
 777                      //
 778                      // and throw if required:
 779                      //
 780                      if(0 == (this->flags() & regex_constants::no_except))
 781                      {
 782                         std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
 783                         boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
 784                         e.raise();
 785                      }
 786                   }
 787                }
 788             }
 789          }
 790          break;
 791       case syntax_element_recurse:
 792          {
 793             bool ok = false;
 794             re_syntax_base* p = base;
 795             std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
 796             if(idx > 10000)
 797             {
 798                //
 799                // There may be more than one capture group with this hash, just do what Perl
 800                // does and recurse to the leftmost:
 801                //
 802                idx = m_pdata->get_id(static_cast<int>(idx));
 803             }
 804             if(idx < 0)
 805             {
 806                ok = false;
 807             }
 808             else
 809             {
 810                while(p)
 811                {
 812                   if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
 813                   {
 814                      //
 815                      // We've found the target of the recursion, set the jump target:
 816                      //
 817                      static_cast<re_jump*>(state)->alt.p = p;
 818                      ok = true;
 819                      //
 820                      // Now scan the target for nested repeats:
 821                      //
 822                      p = p->next.p;
 823                      int next_rep_id = 0;
 824                      while(p)
 825                      {
 826                         switch(p->type)
 827                         {
 828                         case syntax_element_rep:
 829                         case syntax_element_dot_rep:
 830                         case syntax_element_char_rep:
 831                         case syntax_element_short_set_rep:
 832                         case syntax_element_long_set_rep:
 833                            next_rep_id = static_cast<re_repeat*>(p)->state_id;
 834                            break;
 835                         case syntax_element_endmark:
 836                            if(static_cast<const re_brace*>(p)->index == idx)
 837                               next_rep_id = -1;
 838                            break;
 839                         default:
 840                            break;
 841                         }
 842                         if(next_rep_id)
 843                            break;
 844                         p = p->next.p;
 845                      }
 846                      if(next_rep_id > 0)
 847                      {
 848                         static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
 849                      }
 850
 851                      break;
 852                   }
 853                   p = p->next.p;
 854                }
 855             }
 856             if(!ok)
 857             {
 858                // recursion to sub-expression that doesn't exist:
 859                if(0 == this->m_pdata->m_status) // update the error code if not already set
 860                   this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
 861                //
 862                // clear the expression, we should be empty:
 863                //
 864                this->m_pdata->m_expression = 0;
 865                this->m_pdata->m_expression_len = 0;
 866                //
 867                // and throw if required:
 868                //
 869                if(0 == (this->flags() & regex_constants::no_except))
 870                {
 871                   std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
 872                   boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
 873                   e.raise();
 874                }
 875             }
 876          }
 877          break;
 878       default:
 879          break;
 880       }
 881       state = state->next.p;
 882    }
 883 }
 884
 885 template <class charT, class traits>
 886 void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
 887 {
 888    // non-recursive implementation:
 889    // create the last map in the machine first, so that earlier maps
 890    // can make use of the result...
 891    //
 892    // This was originally a recursive implementation, but that caused stack
 893    // overflows with complex expressions on small stacks (think COM+).
 894
 895    // start by saving the case setting:
 896    bool l_icase = m_icase;
 897    std::vector<std::pair<bool, re_syntax_base*> > v;
 898
 899    while(state)
 900    {
 901       switch(state->type)
 902       {
 903       case syntax_element_toggle_case:
 904          // we need to track case changes here:
 905          m_icase = static_cast<re_case*>(state)->icase;
 906          state = state->next.p;
 907          continue;
 908       case syntax_element_alt:
 909       case syntax_element_rep:
 910       case syntax_element_dot_rep:
 911       case syntax_element_char_rep:
 912       case syntax_element_short_set_rep:
 913       case syntax_element_long_set_rep:
 914          // just push the state onto our stack for now:
 915          v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
 916          state = state->next.p;
 917          break;
 918       case syntax_element_backstep:
 919          // we need to calculate how big the backstep is:
 920          static_cast<re_brace*>(state)->index
 921             = this->calculate_backstep(state->next.p);
 922          if(static_cast<re_brace*>(state)->index < 0)
 923          {
 924             // Oops error:
 925             if(0 == this->m_pdata->m_status) // update the error code if not already set
 926                this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
 927             //
 928             // clear the expression, we should be empty:
 929             //
 930             this->m_pdata->m_expression = 0;
 931             this->m_pdata->m_expression_len = 0;
 932             //
 933             // and throw if required:
 934             //
 935             if(0 == (this->flags() & regex_constants::no_except))
 936             {
 937                std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
 938                boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
 939                e.raise();
 940             }
 941          }
 942          BOOST_FALLTHROUGH;
 943       default:
 944          state = state->next.p;
 945       }
 946    }
 947
 948    // now work through our list, building all the maps as we go:
 949    while(v.size())
 950    {
 951       // Initialize m_recursion_checks if we need it:
 952       if(m_has_recursions)
 953          m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
 954
 955       const std::pair<bool, re_syntax_base*>& p = v.back();
 956       m_icase = p.first;
 957       state = p.second;
 958       v.pop_back();
 959
 960       // Build maps:
 961       m_bad_repeats = 0;
 962       create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
 963       m_bad_repeats = 0;
 964
 965       if(m_has_recursions)
 966          m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
 967       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);
 968       // adjust the type of the state to allow for faster matching:
 969       state->type = this->get_repeat_type(state);
 970    }
 971    // restore case sensitivity:
 972    m_icase = l_icase;
 973 }
 974
 975 template <class charT, class traits>
 976 int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
 977 {
 978    typedef typename traits::char_class_type m_type;
 979    int result = 0;
 980    while(state)
 981    {
 982       switch(state->type)
 983       {
 984       case syntax_element_startmark:
 985          if((static_cast<re_brace*>(state)->index == -1)
 986             || (static_cast<re_brace*>(state)->index == -2))
 987          {
 988             state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
 989             continue;
 990          }
 991          else if(static_cast<re_brace*>(state)->index == -3)
 992          {
 993             state = state->next.p->next.p;
 994             continue;
 995          }
 996          break;
 997       case syntax_element_endmark:
 998          if((static_cast<re_brace*>(state)->index == -1)
 999             || (static_cast<re_brace*>(state)->index == -2))
1000             return result;
1001          break;
1002       case syntax_element_literal:
1003          result += static_cast<re_literal*>(state)->length;
1004          break;
1005       case syntax_element_wild:
1006       case syntax_element_set:
1007          result += 1;
1008          break;
1009       case syntax_element_dot_rep:
1010       case syntax_element_char_rep:
1011       case syntax_element_short_set_rep:
1012       case syntax_element_backref:
1013       case syntax_element_rep:
1014       case syntax_element_combining:
1015       case syntax_element_long_set_rep:
1016       case syntax_element_backstep:
1017          {
1018             re_repeat* rep = static_cast<re_repeat *>(state);
1019             // adjust the type of the state to allow for faster matching:
1020             state->type = this->get_repeat_type(state);
1021             if((state->type == syntax_element_dot_rep)
1022                || (state->type == syntax_element_char_rep)
1023                || (state->type == syntax_element_short_set_rep))
1024             {
1025                if(rep->max != rep->min)
1026                   return -1;
1027                result += static_cast<int>(rep->min);
1028                state = rep->alt.p;
1029                continue;
1030             }
1031             else if(state->type == syntax_element_long_set_rep)
1032             {
1033                BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1034                if(static_cast<re_set_long<m_type>*>(rep->next.p)->singleton == 0)
1035                   return -1;
1036                if(rep->max != rep->min)
1037                   return -1;
1038                result += static_cast<int>(rep->min);
1039                state = rep->alt.p;
1040                continue;
1041             }
1042          }
1043          return -1;
1044       case syntax_element_long_set:
1045          if(static_cast<re_set_long<m_type>*>(state)->singleton == 0)
1046             return -1;
1047          result += 1;
1048          break;
1049       case syntax_element_jump:
1050          state = static_cast<re_jump*>(state)->alt.p;
1051          continue;
1052       case syntax_element_alt:
1053          {
1054             int r1 = calculate_backstep(state->next.p);
1055             int r2 = calculate_backstep(static_cast<re_alt*>(state)->alt.p);
1056             if((r1 < 0) || (r1 != r2))
1057                return -1;
1058             return result + r1;
1059          }
1060       default:
1061          break;
1062       }
1063       state = state->next.p;
1064    }
1065    return -1;
1066 }
1067
1068 template <class charT, class traits>
1069 void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
1070 {
1071    int not_last_jump = 1;
1072    re_syntax_base* recursion_start = 0;
1073    int recursion_sub = 0;
1074    re_syntax_base* recursion_restart = 0;
1075
1076    // track case sensitivity:
1077    bool l_icase = m_icase;
1078
1079    while(state)
1080    {
1081       switch(state->type)
1082       {
1083       case syntax_element_toggle_case:
1084          l_icase = static_cast<re_case*>(state)->icase;
1085          state = state->next.p;
1086          break;
1087       case syntax_element_literal:
1088       {
1089          // don't set anything in *pnull, set each element in l_map
1090          // that could match the first character in the literal:
1091          if(l_map)
1092          {
1093             l_map[0] |= mask_init;
1094             charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
1095             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1096             {
1097                if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
1098                   l_map[i] |= mask;
1099             }
1100          }
1101          return;
1102       }
1103       case syntax_element_end_line:
1104       {
1105          // next character must be a line separator (if there is one):
1106          if(l_map)
1107          {
1108             l_map[0] |= mask_init;
1109             l_map[static_cast<unsigned>('\n')] |= mask;
1110             l_map[static_cast<unsigned>('\r')] |= mask;
1111             l_map[static_cast<unsigned>('\f')] |= mask;
1112             l_map[0x85] |= mask;
1113          }
1114          // now figure out if we can match a NULL string at this point:
1115          if(pnull)
1116             create_startmap(state->next.p, 0, pnull, mask);
1117          return;
1118       }
1119       case syntax_element_recurse:
1120          {
1121             BOOST_ASSERT(static_cast<const re_jump*>(state)->alt.p->type == syntax_element_startmark);
1122             recursion_sub = static_cast<re_brace*>(static_cast<const re_jump*>(state)->alt.p)->index;
1123             if(m_recursion_checks[recursion_sub] & 1u)
1124             {
1125                // Infinite recursion!!
1126                if(0 == this->m_pdata->m_status) // update the error code if not already set
1127                   this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
1128                //
1129                // clear the expression, we should be empty:
1130                //
1131                this->m_pdata->m_expression = 0;
1132                this->m_pdata->m_expression_len = 0;
1133                //
1134                // and throw if required:
1135                //
1136                if(0 == (this->flags() & regex_constants::no_except))
1137                {
1138                   std::string message = "Encountered an infinite recursion.";
1139                   boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
1140                   e.raise();
1141                }
1142             }
1143             else if(recursion_start == 0)
1144             {
1145                recursion_start = state;
1146                recursion_restart = state->next.p;
1147                state = static_cast<re_jump*>(state)->alt.p;
1148                m_recursion_checks[recursion_sub] |= 1u;
1149                break;
1150             }
1151             m_recursion_checks[recursion_sub] |= 1u;
1152             // can't handle nested recursion here...
1153             BOOST_FALLTHROUGH;
1154          }
1155       case syntax_element_backref:
1156          // can be null, and any character can match:
1157          if(pnull)
1158             *pnull |= mask;
1159          BOOST_FALLTHROUGH;
1160       case syntax_element_wild:
1161       {
1162          // can't be null, any character can match:
1163          set_all_masks(l_map, mask);
1164          return;
1165       }
1166       case syntax_element_accept:
1167       case syntax_element_match:
1168       {
1169          // must be null, any character can match:
1170          set_all_masks(l_map, mask);
1171          if(pnull)
1172             *pnull |= mask;
1173          return;
1174       }
1175       case syntax_element_word_start:
1176       {
1177          // recurse, then AND with all the word characters:
1178          create_startmap(state->next.p, l_map, pnull, mask);
1179          if(l_map)
1180          {
1181             l_map[0] |= mask_init;
1182             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1183             {
1184                if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
1185                   l_map[i] &= static_cast<unsigned char>(~mask);
1186             }
1187          }
1188          return;
1189       }
1190       case syntax_element_word_end:
1191       {
1192          // recurse, then AND with all the word characters:
1193          create_startmap(state->next.p, l_map, pnull, mask);
1194          if(l_map)
1195          {
1196             l_map[0] |= mask_init;
1197             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1198             {
1199                if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
1200                   l_map[i] &= static_cast<unsigned char>(~mask);
1201             }
1202          }
1203          return;
1204       }
1205       case syntax_element_buffer_end:
1206       {
1207          // we *must be null* :
1208          if(pnull)
1209             *pnull |= mask;
1210          return;
1211       }
1212       case syntax_element_long_set:
1213          if(l_map)
1214          {
1215             typedef typename traits::char_class_type m_type;
1216             if(static_cast<re_set_long<m_type>*>(state)->singleton)
1217             {
1218                l_map[0] |= mask_init;
1219                for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1220                {
1221                   charT c = static_cast<charT>(i);
1222                   if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<m_type>*>(state), *m_pdata, l_icase))
1223                      l_map[i] |= mask;
1224                }
1225             }
1226             else
1227                set_all_masks(l_map, mask);
1228          }
1229          return;
1230       case syntax_element_set:
1231          if(l_map)
1232          {
1233             l_map[0] |= mask_init;
1234             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1235             {
1236                if(static_cast<re_set*>(state)->_map[
1237                   static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1238                   l_map[i] |= mask;
1239             }
1240          }
1241          return;
1242       case syntax_element_jump:
1243          // take the jump:
1244          state = static_cast<re_alt*>(state)->alt.p;
1245          not_last_jump = -1;
1246          break;
1247       case syntax_element_alt:
1248       case syntax_element_rep:
1249       case syntax_element_dot_rep:
1250       case syntax_element_char_rep:
1251       case syntax_element_short_set_rep:
1252       case syntax_element_long_set_rep:
1253          {
1254             re_alt* rep = static_cast<re_alt*>(state);
1255             if(rep->_map[0] & mask_init)
1256             {
1257                if(l_map)
1258                {
1259                   // copy previous results:
1260                   l_map[0] |= mask_init;
1261                   for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1262                   {
1263                      if(rep->_map[i] & mask_any)
1264                         l_map[i] |= mask;
1265                   }
1266                }
1267                if(pnull)
1268                {
1269                   if(rep->can_be_null & mask_any)
1270                      *pnull |= mask;
1271                }
1272             }
1273             else
1274             {
1275                // we haven't created a startmap for this alternative yet
1276                // so take the union of the two options:
1277                if(is_bad_repeat(state))
1278                {
1279                   set_all_masks(l_map, mask);
1280                   if(pnull)
1281                      *pnull |= mask;
1282                   return;
1283                }
1284                set_bad_repeat(state);
1285                create_startmap(state->next.p, l_map, pnull, mask);
1286                if((state->type == syntax_element_alt)
1287                   || (static_cast<re_repeat*>(state)->min == 0)
1288                   || (not_last_jump == 0))
1289                   create_startmap(rep->alt.p, l_map, pnull, mask);
1290             }
1291          }
1292          return;
1293       case syntax_element_soft_buffer_end:
1294          // match newline or null:
1295          if(l_map)
1296          {
1297             l_map[0] |= mask_init;
1298             l_map[static_cast<unsigned>('\n')] |= mask;
1299             l_map[static_cast<unsigned>('\r')] |= mask;
1300          }
1301          if(pnull)
1302             *pnull |= mask;
1303          return;
1304       case syntax_element_endmark:
1305          // need to handle independent subs as a special case:
1306          if(static_cast<re_brace*>(state)->index < 0)
1307          {
1308             // can be null, any character can match:
1309             set_all_masks(l_map, mask);
1310             if(pnull)
1311                *pnull |= mask;
1312             return;
1313          }
1314          else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
1315          {
1316             // recursion termination:
1317             recursion_start = 0;
1318             state = recursion_restart;
1319             break;
1320          }
1321
1322          //
1323          // Normally we just go to the next state... but if this sub-expression is
1324          // the target of a recursion, then we might be ending a recursion, in which
1325          // case we should check whatever follows that recursion, as well as whatever
1326          // follows this state:
1327          //
1328          if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
1329          {
1330             bool ok = false;
1331             re_syntax_base* p = m_pdata->m_first_state;
1332             while(p)
1333             {
1334                if(p->type == syntax_element_recurse)
1335                {
1336                   re_brace* p2 = static_cast<re_brace*>(static_cast<re_jump*>(p)->alt.p);
1337                   if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
1338                   {
1339                      ok = true;
1340                      break;
1341                   }
1342                }
1343                p = p->next.p;
1344             }
1345             if(ok && ((m_recursion_checks[static_cast<re_brace*>(state)->index] & 2u) == 0))
1346             {
1347                m_recursion_checks[static_cast<re_brace*>(state)->index] |= 2u;
1348                create_startmap(p->next.p, l_map, pnull, mask);
1349             }
1350          }
1351          state = state->next.p;
1352          break;
1353
1354       case syntax_element_commit:
1355          set_all_masks(l_map, mask);
1356          // Continue scanning so we can figure out whether we can be null:
1357          state = state->next.p;
1358          break;
1359       case syntax_element_startmark:
1360          // need to handle independent subs as a special case:
1361          if(static_cast<re_brace*>(state)->index == -3)
1362          {
1363             state = state->next.p->next.p;
1364             break;
1365          }
1366          BOOST_FALLTHROUGH;
1367       default:
1368          state = state->next.p;
1369       }
1370       ++not_last_jump;
1371    }
1372 }
1373
1374 template <class charT, class traits>
1375 unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1376 {
1377    //
1378    // find out how the machine starts, so we can optimise the search:
1379    //
1380    while(state)
1381    {
1382       switch(state->type)
1383       {
1384       case syntax_element_startmark:
1385       case syntax_element_endmark:
1386          state = state->next.p;
1387          continue;
1388       case syntax_element_start_line:
1389          return regbase::restart_line;
1390       case syntax_element_word_start:
1391          return regbase::restart_word;
1392       case syntax_element_buffer_start:
1393          return regbase::restart_buf;
1394       case syntax_element_restart_continue:
1395          return regbase::restart_continue;
1396       default:
1397          state = 0;
1398          continue;
1399       }
1400    }
1401    return regbase::restart_any;
1402 }
1403
1404 template <class charT, class traits>
1405 void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1406 {
1407    //
1408    // set mask in all of bits elements,
1409    // if bits[0] has mask_init not set then we can
1410    // optimise this to a call to memset:
1411    //
1412    if(bits)
1413    {
1414       if(bits[0] == 0)
1415          (std::memset)(bits, mask, 1u << CHAR_BIT);
1416       else
1417       {
1418          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1419             bits[i] |= mask;
1420       }
1421       bits[0] |= mask_init;
1422    }
1423 }
1424
1425 template <class charT, class traits>
1426 bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1427 {
1428    switch(pt->type)
1429    {
1430    case syntax_element_rep:
1431    case syntax_element_dot_rep:
1432    case syntax_element_char_rep:
1433    case syntax_element_short_set_rep:
1434    case syntax_element_long_set_rep:
1435       {
1436          unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1437          if(state_id >= sizeof(m_bad_repeats) * CHAR_BIT)
1438             return true;  // run out of bits, assume we can't traverse this one.
1439          static const boost::uintmax_t one = 1uL;
1440          return m_bad_repeats & (one << state_id);
1441       }
1442    default:
1443       return false;
1444    }
1445 }
1446
1447 template <class charT, class traits>
1448 void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1449 {
1450    switch(pt->type)
1451    {
1452    case syntax_element_rep:
1453    case syntax_element_dot_rep:
1454    case syntax_element_char_rep:
1455    case syntax_element_short_set_rep:
1456    case syntax_element_long_set_rep:
1457       {
1458          unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1459          static const boost::uintmax_t one = 1uL;
1460          if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
1461             m_bad_repeats |= (one << state_id);
1462       }
1463       break;
1464    default:
1465       break;
1466    }
1467 }
1468
1469 template <class charT, class traits>
1470 syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1471 {
1472    typedef typename traits::char_class_type m_type;
1473    if(state->type == syntax_element_rep)
1474    {
1475       // check to see if we are repeating a single state:
1476       if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1477       {
1478          switch(state->next.p->type)
1479          {
1480          case BOOST_REGEX_DETAIL_NS::syntax_element_wild:
1481             return BOOST_REGEX_DETAIL_NS::syntax_element_dot_rep;
1482          case BOOST_REGEX_DETAIL_NS::syntax_element_literal:
1483             return BOOST_REGEX_DETAIL_NS::syntax_element_char_rep;
1484          case BOOST_REGEX_DETAIL_NS::syntax_element_set:
1485             return BOOST_REGEX_DETAIL_NS::syntax_element_short_set_rep;
1486          case BOOST_REGEX_DETAIL_NS::syntax_element_long_set:
1487             if(static_cast<BOOST_REGEX_DETAIL_NS::re_set_long<m_type>*>(state->next.p)->singleton)
1488                return BOOST_REGEX_DETAIL_NS::syntax_element_long_set_rep;
1489             break;
1490          default:
1491             break;
1492          }
1493       }
1494    }
1495    return state->type;
1496 }
1497
1498 template <class charT, class traits>
1499 void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1500 {
1501    // enumerate our states, and see if we have a leading repeat
1502    // for which failed search restarts can be optimised;
1503    do
1504    {
1505       switch(state->type)
1506       {
1507       case syntax_element_startmark:
1508          if(static_cast<re_brace*>(state)->index >= 0)
1509          {
1510             state = state->next.p;
1511             continue;
1512          }
1513          if((static_cast<re_brace*>(state)->index == -1)
1514             || (static_cast<re_brace*>(state)->index == -2))
1515          {
1516             // skip past the zero width assertion:
1517             state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
1518             continue;
1519          }
1520          if(static_cast<re_brace*>(state)->index == -3)
1521          {
1522             // Have to skip the leading jump state:
1523             state = state->next.p->next.p;
1524             continue;
1525          }
1526          return;
1527       case syntax_element_endmark:
1528       case syntax_element_start_line:
1529       case syntax_element_end_line:
1530       case syntax_element_word_boundary:
1531       case syntax_element_within_word:
1532       case syntax_element_word_start:
1533       case syntax_element_word_end:
1534       case syntax_element_buffer_start:
1535       case syntax_element_buffer_end:
1536       case syntax_element_restart_continue:
1537          state = state->next.p;
1538          break;
1539       case syntax_element_dot_rep:
1540       case syntax_element_char_rep:
1541       case syntax_element_short_set_rep:
1542       case syntax_element_long_set_rep:
1543          if(this->m_has_backrefs == 0)
1544             static_cast<re_repeat*>(state)->leading = true;
1545          BOOST_FALLTHROUGH;
1546       default:
1547          return;
1548       }
1549    }while(state);
1550 }
1551
1552
1553 } // namespace BOOST_REGEX_DETAIL_NS
1554
1555 } // namespace boost
1556
1557 #ifdef BOOST_MSVC
1558 #  pragma warning(pop)
1559 #endif
1560
1561 #ifdef BOOST_MSVC
1562 #pragma warning(push)
1563 #pragma warning(disable: 4103)
1564 #endif
1565 #ifdef BOOST_HAS_ABI_HEADERS
1566 #  include BOOST_ABI_SUFFIX
1567 #endif
1568 #ifdef BOOST_MSVC
1569 #pragma warning(pop)
1570 #endif
1571
1572 #endif
1573