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