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_HAS_ABI_HEADERS
  24 #  include BOOST_ABI_PREFIX
  25 #endif
  26
  27 namespace boost{
  28
  29 namespace re_detail{
  30
  31 template <class charT>
  32 struct digraph : public std::pair<charT, charT>
  33 {
  34    digraph() : std::pair<charT, charT>(0, 0){}
  35    digraph(charT c1) : std::pair<charT, charT>(c1, 0){}
  36    digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
  37    {}
  38 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
  39    digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
  40 #endif
  41    template <class Seq>
  42    digraph(const Seq& s) : std::pair<charT, charT>()
  43    {
  44       BOOST_ASSERT(s.size() <= 2);
  45       BOOST_ASSERT(s.size());
  46       this->first = s[0];
  47       this->second = (s.size() > 1) ? s[1] : 0;
  48    }
  49 };
  50
  51 template <class charT, class traits>
  52 class basic_char_set
  53 {
  54 public:
  55    typedef digraph<charT>                   digraph_type;
  56    typedef typename traits::string_type     string_type;
  57    typedef typename traits::char_class_type mask_type;
  58
  59    basic_char_set()
  60    {
  61       m_negate = false;
  62       m_has_digraphs = false;
  63       m_classes = 0;
  64       m_negated_classes = 0;
  65       m_empty = true;
  66    }
  67
  68    void add_single(const digraph_type& s)
  69    {
  70       m_singles.insert(m_singles.end(), s);
  71       if(s.second)
  72          m_has_digraphs = true;
  73       m_empty = false;
  74    }
  75    void add_range(const digraph_type& first, const digraph_type& end)
  76    {
  77       m_ranges.insert(m_ranges.end(), first);
  78       m_ranges.insert(m_ranges.end(), end);
  79       if(first.second)
  80       {
  81          m_has_digraphs = true;
  82          add_single(first);
  83       }
  84       if(end.second)
  85       {
  86          m_has_digraphs = true;
  87          add_single(end);
  88       }
  89       m_empty = false;
  90    }
  91    void add_class(mask_type m)
  92    {
  93       m_classes |= m;
  94       m_empty = false;
  95    }
  96    void add_negated_class(mask_type m)
  97    {
  98       m_negated_classes |= m;
  99       m_empty = false;
 100    }
 101    void add_equivalent(const digraph_type& s)
 102    {
 103       m_equivalents.insert(m_equivalents.end(), s);
 104       if(s.second)
 105       {
 106          m_has_digraphs = true;
 107          add_single(s);
 108       }
 109       m_empty = false;
 110    }
 111    void negate()
 112    {
 113       m_negate = true;
 114       //m_empty = false;
 115    }
 116
 117    //
 118    // accessor functions:
 119    //
 120    bool has_digraphs()const
 121    {
 122       return m_has_digraphs;
 123    }
 124    bool is_negated()const
 125    {
 126       return m_negate;
 127    }
 128    typedef typename std::vector<digraph_type>::const_iterator  list_iterator;
 129    list_iterator singles_begin()const
 130    {
 131       return m_singles.begin();
 132    }
 133    list_iterator singles_end()const
 134    {
 135       return m_singles.end();
 136    }
 137    list_iterator ranges_begin()const
 138    {
 139       return m_ranges.begin();
 140    }
 141    list_iterator ranges_end()const
 142    {
 143       return m_ranges.end();
 144    }
 145    list_iterator equivalents_begin()const
 146    {
 147       return m_equivalents.begin();
 148    }
 149    list_iterator equivalents_end()const
 150    {
 151       return m_equivalents.end();
 152    }
 153    mask_type classes()const
 154    {
 155       return m_classes;
 156    }
 157    mask_type negated_classes()const
 158    {
 159       return m_negated_classes;
 160    }
 161    bool empty()const
 162    {
 163       return m_empty;
 164    }
 165 private:
 166    std::vector<digraph_type> m_singles;         // a list of single characters to match
 167    std::vector<digraph_type> m_ranges;          // a list of end points of our ranges
 168    bool                      m_negate;          // true if the set is to be negated
 169    bool                      m_has_digraphs;    // true if we have digraphs present
 170    mask_type                 m_classes;         // character classes to match
 171    mask_type                 m_negated_classes; // negated character classes to match
 172    bool                      m_empty;           // whether we've added anything yet
 173    std::vector<digraph_type> m_equivalents;     // a list of equivalence classes
 174 };
 175
 176 template <class charT, class traits>
 177 class basic_regex_creator
 178 {
 179 public:
 180    basic_regex_creator(regex_data<charT, traits>* data);
 181    std::ptrdiff_t getoffset(void* addr)
 182    {
 183       return getoffset(addr, m_pdata->m_data.data());
 184    }
 185    std::ptrdiff_t getoffset(const void* addr, const void* base)
 186    {
 187       return static_cast<const char*>(addr) - static_cast<const char*>(base);
 188    }
 189    re_syntax_base* getaddress(std::ptrdiff_t off)
 190    {
 191       return getaddress(off, m_pdata->m_data.data());
 192    }
 193    re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
 194    {
 195       return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
 196    }
 197    void init(unsigned l_flags)
 198    {
 199       m_pdata->m_flags = l_flags;
 200       m_icase = l_flags & regex_constants::icase;
 201    }
 202    regbase::flag_type flags()
 203    {
 204       return m_pdata->m_flags;
 205    }
 206    void flags(regbase::flag_type f)
 207    {
 208       m_pdata->m_flags = f;
 209       if(m_icase != static_cast<bool>(f & regbase::icase))
 210       {
 211          m_icase = static_cast<bool>(f & regbase::icase);
 212       }
 213    }
 214    re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
 215    re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
 216    re_literal* append_literal(charT c);
 217    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
 218    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
 219    re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
 220    void finalize(const charT* p1, const charT* p2);
 221 protected:
 222    regex_data<charT, traits>*    m_pdata;              // pointer to the basic_regex_data struct we are filling in
 223    const ::boost::regex_traits_wrapper<traits>&
 224                                  m_traits;             // convenience reference to traits class
 225    re_syntax_base*               m_last_state;         // the last state we added
 226    bool                          m_icase;              // true for case insensitive matches
 227    unsigned                      m_repeater_id;        // the id of the next repeater
 228    bool                          m_has_backrefs;       // true if there are actually any backrefs
 229    unsigned                      m_backrefs;           // bitmask of permitted backrefs
 230    boost::uintmax_t              m_bad_repeats;        // bitmask of repeats we can't deduce a startmap for;
 231    typename traits::char_class_type m_word_mask;       // mask used to determine if a character is a word character
 232    typename traits::char_class_type m_mask_space;      // mask used to determine if a character is a word character
 233    typename traits::char_class_type m_lower_mask;       // mask used to determine if a character is a lowercase character
 234    typename traits::char_class_type m_upper_mask;      // mask used to determine if a character is an uppercase character
 235    typename traits::char_class_type m_alpha_mask;      // mask used to determine if a character is an alphabetic character
 236 private:
 237    basic_regex_creator& operator=(const basic_regex_creator&);
 238    basic_regex_creator(const basic_regex_creator&);
 239
 240    void fixup_pointers(re_syntax_base* state);
 241    void create_startmaps(re_syntax_base* state);
 242    int calculate_backstep(re_syntax_base* state);
 243    void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
 244    unsigned get_restart_type(re_syntax_base* state);
 245    void set_all_masks(unsigned char* bits, unsigned char);
 246    bool is_bad_repeat(re_syntax_base* pt);
 247    void set_bad_repeat(re_syntax_base* pt);
 248    syntax_element_type get_repeat_type(re_syntax_base* state);
 249    void probe_leading_repeat(re_syntax_base* state);
 250 };
 251
 252 template <class charT, class traits>
 253 basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
 254    : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_repeater_id(0), m_has_backrefs(false), m_backrefs(0)
 255 {
 256    m_pdata->m_data.clear();
 257    m_pdata->m_status = ::boost::regex_constants::error_ok;
 258    static const charT w = 'w';
 259    static const charT s = 's';
 260    static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
 261    static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
 262    static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
 263    m_word_mask = m_traits.lookup_classname(&w, &w +1);
 264    m_mask_space = m_traits.lookup_classname(&s, &s +1);
 265    m_lower_mask = m_traits.lookup_classname(l, l + 5);
 266    m_upper_mask = m_traits.lookup_classname(u, u + 5);
 267    m_alpha_mask = m_traits.lookup_classname(a, a + 5);
 268    m_pdata->m_word_mask = m_word_mask;
 269    BOOST_ASSERT(m_word_mask != 0);
 270    BOOST_ASSERT(m_mask_space != 0);
 271    BOOST_ASSERT(m_lower_mask != 0);
 272    BOOST_ASSERT(m_upper_mask != 0);
 273    BOOST_ASSERT(m_alpha_mask != 0);
 274 }
 275
 276 template <class charT, class traits>
 277 re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
 278 {
 279    // if the state is a backref then make a note of it:
 280    if(t == syntax_element_backref)
 281       this->m_has_backrefs = true;
 282    // append a new state, start by aligning our last one:
 283    m_pdata->m_data.align();
 284    // set the offset to the next state in our last one:
 285    if(m_last_state)
 286       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
 287    // now actually extent our data:
 288    m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
 289    // fill in boilerplate options in the new state:
 290    m_last_state->next.i = 0;
 291    m_last_state->type = t;
 292    return m_last_state;
 293 }
 294
 295 template <class charT, class traits>
 296 re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
 297 {
 298    // append a new state, start by aligning our last one:
 299    m_pdata->m_data.align();
 300    // set the offset to the next state in our last one:
 301    if(m_last_state)
 302       m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
 303    // remember the last state position:
 304    std::ptrdiff_t off = getoffset(m_last_state) + s;
 305    // now actually insert our data:
 306    re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
 307    // fill in boilerplate options in the new state:
 308    new_state->next.i = s;
 309    new_state->type = t;
 310    m_last_state = getaddress(off);
 311    return new_state;
 312 }
 313
 314 template <class charT, class traits>
 315 re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
 316 {
 317    re_literal* result;
 318    // start by seeing if we have an existing re_literal we can extend:
 319    if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
 320    {
 321       // no existing re_literal, create a new one:
 322       result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
 323       result->length = 1;
 324       *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
 325    }
 326    else
 327    {
 328       // we have an existing re_literal, extend it:
 329       std::ptrdiff_t off = getoffset(m_last_state);
 330       m_pdata->m_data.extend(sizeof(charT));
 331       m_last_state = result = static_cast<re_literal*>(getaddress(off));
 332       charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
 333       characters[result->length] = m_traits.translate(c, m_icase);
 334       ++(result->length);
 335    }
 336    return result;
 337 }
 338
 339 template <class charT, class traits>
 340 inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
 341    const basic_char_set<charT, traits>& char_set)
 342 {
 343    typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
 344    return char_set.has_digraphs()
 345       ? append_set(char_set, static_cast<mpl::false_*>(0))
 346       : append_set(char_set, static_cast<truth_type*>(0));
 347 }
 348
 349 template <class charT, class traits>
 350 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
 351    const basic_char_set<charT, traits>& char_set, mpl::false_*)
 352 {
 353    typedef typename traits::string_type string_type;
 354    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
 355    typedef typename traits::char_class_type mask_type;
 356
 357    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>)));
 358    //
 359    // fill in the basics:
 360    //
 361    result->csingles = static_cast<unsigned int>(::boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end()));
 362    result->cranges = static_cast<unsigned int>(::boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
 363    result->cequivalents = static_cast<unsigned int>(::boost::re_detail::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
 364    result->cclasses = char_set.classes();
 365    result->cnclasses = char_set.negated_classes();
 366    if(flags() & regbase::icase)
 367    {
 368       // adjust classes as needed:
 369       if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
 370          result->cclasses |= m_alpha_mask;
 371       if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
 372          result->cnclasses |= m_alpha_mask;
 373    }
 374
 375    result->isnot = char_set.is_negated();
 376    result->singleton = !char_set.has_digraphs();
 377    //
 378    // remember where the state is for later:
 379    //
 380    std::ptrdiff_t offset = getoffset(result);
 381    //
 382    // now extend with all the singles:
 383    //
 384    item_iterator first, last;
 385    first = char_set.singles_begin();
 386    last = char_set.singles_end();
 387    while(first != last)
 388    {
 389       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (first->second ? 3 : 2)));
 390       p[0] = m_traits.translate(first->first, m_icase);
 391       if(first->second)
 392       {
 393          p[1] = m_traits.translate(first->second, m_icase);
 394          p[2] = 0;
 395       }
 396       else
 397          p[1] = 0;
 398       ++first;
 399    }
 400    //
 401    // now extend with all the ranges:
 402    //
 403    first = char_set.ranges_begin();
 404    last = char_set.ranges_end();
 405    while(first != last)
 406    {
 407       // first grab the endpoints of the range:
 408       digraph<charT> c1 = *first;
 409       c1.first = this->m_traits.translate(c1.first, this->m_icase);
 410       c1.second = this->m_traits.translate(c1.second, this->m_icase);
 411       ++first;
 412       digraph<charT> c2 = *first;
 413       c2.first = this->m_traits.translate(c2.first, this->m_icase);
 414       c2.second = this->m_traits.translate(c2.second, this->m_icase);
 415       ++first;
 416       string_type s1, s2;
 417       // different actions now depending upon whether collation is turned on:
 418       if(flags() & regex_constants::collate)
 419       {
 420          // we need to transform our range into sort keys:
 421 #if BOOST_WORKAROUND(__GNUC__, < 3)
 422          string_type in(3, charT(0));
 423          in[0] = c1.first;
 424          in[1] = c1.second;
 425          s1 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
 426          in[0] = c2.first;
 427          in[1] = c2.second;
 428          s2 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
 429 #else
 430          charT a1[3] = { c1.first, c1.second, charT(0), };
 431          charT a2[3] = { c2.first, c2.second, charT(0), };
 432          s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
 433          s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
 434 #endif
 435          if(s1.size() == 0)
 436             s1 = string_type(1, charT(0));
 437          if(s2.size() == 0)
 438             s2 = string_type(1, charT(0));
 439       }
 440       else
 441       {
 442          if(c1.second)
 443          {
 444             s1.insert(s1.end(), c1.first);
 445             s1.insert(s1.end(), c1.second);
 446          }
 447          else
 448             s1 = string_type(1, c1.first);
 449          if(c2.second)
 450          {
 451             s2.insert(s2.end(), c2.first);
 452             s2.insert(s2.end(), c2.second);
 453          }
 454          else
 455             s2.insert(s2.end(), c2.first);
 456       }
 457       if(s1 > s2)
 458       {
 459          // Oops error:
 460          return 0;
 461       }
 462       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
 463       re_detail::copy(s1.begin(), s1.end(), p);
 464       p[s1.size()] = charT(0);
 465       p += s1.size() + 1;
 466       re_detail::copy(s2.begin(), s2.end(), p);
 467       p[s2.size()] = charT(0);
 468    }
 469    //
 470    // now process the equivalence classes:
 471    //
 472    first = char_set.equivalents_begin();
 473    last = char_set.equivalents_end();
 474    while(first != last)
 475    {
 476       string_type s;
 477       if(first->second)
 478       {
 479 #if BOOST_WORKAROUND(__GNUC__, < 3)
 480          string_type in(3, charT(0));
 481          in[0] = first->first;
 482          in[1] = first->second;
 483          s = m_traits.transform_primary(in.c_str(), in.c_str()+2);
 484 #else
 485          charT cs[3] = { first->first, first->second, charT(0), };
 486          s = m_traits.transform_primary(cs, cs+2);
 487 #endif
 488       }
 489       else
 490          s = m_traits.transform_primary(&first->first, &first->first+1);
 491       if(s.empty())
 492          return 0;  // invalid or unsupported equivalence class
 493       charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
 494       re_detail::copy(s.begin(), s.end(), p);
 495       p[s.size()] = charT(0);
 496       ++first;
 497    }
 498    //
 499    // finally reset the address of our last state:
 500    //
 501    m_last_state = result = static_cast<re_set_long<mask_type>*>(getaddress(offset));
 502    return result;
 503 }
 504
 505 namespace{
 506
 507 template<class T>
 508 inline bool char_less(T t1, T t2)
 509 {
 510    return t1 < t2;
 511 }
 512 template<>
 513 inline bool char_less<char>(char t1, char t2)
 514 {
 515    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
 516 }
 517 template<>
 518 inline bool char_less<signed char>(signed char t1, signed char t2)
 519 {
 520    return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
 521 }
 522 }
 523
 524 template <class charT, class traits>
 525 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
 526    const basic_char_set<charT, traits>& char_set, mpl::true_*)
 527 {
 528    typedef typename traits::string_type string_type;
 529    typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
 530
 531    re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
 532    bool negate = char_set.is_negated();
 533    std::memset(result->_map, 0, sizeof(result->_map));
 534    //
 535    // handle singles first:
 536    //
 537    item_iterator first, last;
 538    first = char_set.singles_begin();
 539    last = char_set.singles_end();
 540    while(first != last)
 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(first->first, this->m_icase))
 546             result->_map[i] = true;
 547       }
 548       ++first;
 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<charT>(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 mask_type;
 599    mask_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    first = char_set.equivalents_begin();
 636    last = char_set.equivalents_end();
 637    while(first != last)
 638    {
 639       string_type s;
 640       BOOST_ASSERT(static_cast<charT>(0) == first->second);
 641       s = m_traits.transform_primary(&first->first, &first->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       ++first;
 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    // we've added all the states we need, now finish things off.
 667    // start by adding a terminating state:
 668    append_state(syntax_element_match);
 669    // extend storage to store original expression:
 670    std::ptrdiff_t len = p2 - p1;
 671    m_pdata->m_expression_len = len;
 672    charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
 673    m_pdata->m_expression = ps;
 674    re_detail::copy(p1, p2, ps);
 675    ps[p2 - p1] = 0;
 676    // fill in our other data...
 677    // successful parsing implies a zero status:
 678    m_pdata->m_status = 0;
 679    // get the first state of the machine:
 680    m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
 681    // fixup pointers in the machine:
 682    fixup_pointers(m_pdata->m_first_state);
 683    // create nested startmaps:
 684    create_startmaps(m_pdata->m_first_state);
 685    // create main startmap:
 686    std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
 687    m_pdata->m_can_be_null = 0;
 688
 689    m_bad_repeats = 0;
 690    create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
 691    // get the restart type:
 692    m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
 693    // optimise a leading repeat if there is one:
 694    probe_leading_repeat(m_pdata->m_first_state);
 695 }
 696
 697 template <class charT, class traits>
 698 void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
 699 {
 700    while(state)
 701    {
 702       switch(state->type)
 703       {
 704       case syntax_element_rep:
 705       case syntax_element_dot_rep:
 706       case syntax_element_char_rep:
 707       case syntax_element_short_set_rep:
 708       case syntax_element_long_set_rep:
 709          // set the id of this repeat:
 710          static_cast<re_repeat*>(state)->id = m_repeater_id++;
 711          // fall through:
 712       case syntax_element_alt:
 713          std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
 714          static_cast<re_alt*>(state)->can_be_null = 0;
 715          // fall through:
 716       case syntax_element_jump:
 717          static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
 718          // fall through again:
 719       default:
 720          if(state->next.i)
 721             state->next.p = getaddress(state->next.i, state);
 722          else
 723             state->next.p = 0;
 724       }
 725       state = state->next.p;
 726    }
 727 }
 728
 729 template <class charT, class traits>
 730 void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
 731 {
 732    // non-recursive implementation:
 733    // create the last map in the machine first, so that earlier maps
 734    // can make use of the result...
 735    //
 736    // This was originally a recursive implementation, but that caused stack
 737    // overflows with complex expressions on small stacks (think COM+).
 738
 739    // start by saving the case setting:
 740    bool l_icase = m_icase;
 741    std::vector<std::pair<bool, re_syntax_base*> > v;
 742
 743    while(state)
 744    {
 745       switch(state->type)
 746       {
 747       case syntax_element_toggle_case:
 748          // we need to track case changes here:
 749          m_icase = static_cast<re_case*>(state)->icase;
 750          state = state->next.p;
 751          continue;
 752       case syntax_element_alt:
 753       case syntax_element_rep:
 754       case syntax_element_dot_rep:
 755       case syntax_element_char_rep:
 756       case syntax_element_short_set_rep:
 757       case syntax_element_long_set_rep:
 758          // just push the state onto our stack for now:
 759          v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
 760          state = state->next.p;
 761          break;
 762       case syntax_element_backstep:
 763          // we need to calculate how big the backstep is:
 764          static_cast<re_brace*>(state)->index
 765             = this->calculate_backstep(state->next.p);
 766          if(static_cast<re_brace*>(state)->index < 0)
 767          {
 768             // Oops error:
 769             if(0 == this->m_pdata->m_status) // update the error code if not already set
 770                this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
 771             //
 772             // clear the expression, we should be empty:
 773             //
 774             this->m_pdata->m_expression = 0;
 775             this->m_pdata->m_expression_len = 0;
 776             //
 777             // and throw if required:
 778             //
 779             if(0 == (this->flags() & regex_constants::no_except))
 780             {
 781                std::string message = this->m_pdata->m_ptraits->error_string(boost::regex_constants::error_bad_pattern);
 782                boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
 783                e.raise();
 784             }
 785          }
 786          // fall through:
 787       default:
 788          state = state->next.p;
 789       }
 790    }
 791    // now work through our list, building all the maps as we go:
 792    while(v.size())
 793    {
 794       const std::pair<bool, re_syntax_base*>& p = v.back();
 795       m_icase = p.first;
 796       state = p.second;
 797       v.pop_back();
 798
 799       // Build maps:
 800       m_bad_repeats = 0;
 801       create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
 802       m_bad_repeats = 0;
 803       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);
 804       // adjust the type of the state to allow for faster matching:
 805       state->type = this->get_repeat_type(state);
 806    }
 807    // restore case sensitivity:
 808    m_icase = l_icase;
 809 }
 810
 811 template <class charT, class traits>
 812 int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
 813 {
 814    typedef typename traits::char_class_type mask_type;
 815    int result = 0;
 816    while(state)
 817    {
 818       switch(state->type)
 819       {
 820       case syntax_element_startmark:
 821          if((static_cast<re_brace*>(state)->index == -1)
 822             || (static_cast<re_brace*>(state)->index == -2))
 823          {
 824             state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
 825             continue;
 826          }
 827          else if(static_cast<re_brace*>(state)->index == -3)
 828          {
 829             state = state->next.p->next.p;
 830             continue;
 831          }
 832          break;
 833       case syntax_element_endmark:
 834          if((static_cast<re_brace*>(state)->index == -1)
 835             || (static_cast<re_brace*>(state)->index == -2))
 836             return result;
 837          break;
 838       case syntax_element_literal:
 839          result += static_cast<re_literal*>(state)->length;
 840          break;
 841       case syntax_element_wild:
 842       case syntax_element_set:
 843          result += 1;
 844          break;
 845       case syntax_element_dot_rep:
 846       case syntax_element_char_rep:
 847       case syntax_element_short_set_rep:
 848       case syntax_element_backref:
 849       case syntax_element_rep:
 850       case syntax_element_combining:
 851       case syntax_element_long_set_rep:
 852       case syntax_element_backstep:
 853          {
 854             re_repeat* rep = static_cast<re_repeat *>(state);
 855             // adjust the type of the state to allow for faster matching:
 856             state->type = this->get_repeat_type(state);
 857             if((state->type == syntax_element_dot_rep)
 858                || (state->type == syntax_element_char_rep)
 859                || (state->type == syntax_element_short_set_rep))
 860             {
 861                if(rep->max != rep->min)
 862                   return -1;
 863                result += static_cast<int>(rep->min);
 864                state = rep->alt.p;
 865                continue;
 866             }
 867             else if((state->type == syntax_element_long_set_rep))
 868             {
 869                BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
 870                if(static_cast<re_set_long<mask_type>*>(rep->next.p)->singleton == 0)
 871                   return -1;
 872                if(rep->max != rep->min)
 873                   return -1;
 874                result += static_cast<int>(rep->min);
 875                state = rep->alt.p;
 876                continue;
 877             }
 878          }
 879          return -1;
 880       case syntax_element_long_set:
 881          if(static_cast<re_set_long<mask_type>*>(state)->singleton == 0)
 882             return -1;
 883          result += 1;
 884          break;
 885       case syntax_element_jump:
 886          state = static_cast<re_jump*>(state)->alt.p;
 887          continue;
 888       default:
 889          break;
 890       }
 891       state = state->next.p;
 892    }
 893    return -1;
 894 }
 895
 896 template <class charT, class traits>
 897 void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
 898 {
 899    int not_last_jump = 1;
 900
 901    // track case sensitivity:
 902    bool l_icase = m_icase;
 903
 904    while(state)
 905    {
 906       switch(state->type)
 907       {
 908       case syntax_element_toggle_case:
 909          l_icase = static_cast<re_case*>(state)->icase;
 910          state = state->next.p;
 911          break;
 912       case syntax_element_literal:
 913       {
 914          // don't set anything in *pnull, set each element in l_map
 915          // that could match the first character in the literal:
 916          if(l_map)
 917          {
 918             l_map[0] |= mask_init;
 919             charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
 920             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
 921             {
 922                if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
 923                   l_map[i] |= mask;
 924             }
 925          }
 926          return;
 927       }
 928       case syntax_element_end_line:
 929       {
 930          // next character must be a line separator (if there is one):
 931          if(l_map)
 932          {
 933             l_map[0] |= mask_init;
 934             l_map['\n'] |= mask;
 935             l_map['\r'] |= mask;
 936             l_map['\f'] |= mask;
 937             l_map[0x85] |= mask;
 938          }
 939          // now figure out if we can match a NULL string at this point:
 940          if(pnull)
 941             create_startmap(state->next.p, 0, pnull, mask);
 942          return;
 943       }
 944       case syntax_element_backref:
 945          // can be null, and any character can match:
 946          if(pnull)
 947             *pnull |= mask;
 948          // fall through:
 949       case syntax_element_wild:
 950       {
 951          // can't be null, any character can match:
 952          set_all_masks(l_map, mask);
 953          return;
 954       }
 955       case syntax_element_match:
 956       {
 957          // must be null, any character can match:
 958          set_all_masks(l_map, mask);
 959          if(pnull)
 960             *pnull |= mask;
 961          return;
 962       }
 963       case syntax_element_word_start:
 964       {
 965          // recurse, then AND with all the word characters:
 966          create_startmap(state->next.p, l_map, pnull, mask);
 967          if(l_map)
 968          {
 969             l_map[0] |= mask_init;
 970             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
 971             {
 972                if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
 973                   l_map[i] &= static_cast<unsigned char>(~mask);
 974             }
 975          }
 976          return;
 977       }
 978       case syntax_element_word_end:
 979       {
 980          // recurse, then AND with all the word characters:
 981          create_startmap(state->next.p, l_map, pnull, mask);
 982          if(l_map)
 983          {
 984             l_map[0] |= mask_init;
 985             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
 986             {
 987                if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
 988                   l_map[i] &= static_cast<unsigned char>(~mask);
 989             }
 990          }
 991          return;
 992       }
 993       case syntax_element_buffer_end:
 994       {
 995          // we *must be null* :
 996          if(pnull)
 997             *pnull |= mask;
 998          return;
 999       }
1000       case syntax_element_long_set:
1001          if(l_map)
1002          {
1003             typedef typename traits::char_class_type mask_type;
1004             if(static_cast<re_set_long<mask_type>*>(state)->singleton)
1005             {
1006                l_map[0] |= mask_init;
1007                for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1008                {
1009                   charT c = static_cast<charT>(i);
1010                   if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<mask_type>*>(state), *m_pdata, m_icase))
1011                      l_map[i] |= mask;
1012                }
1013             }
1014             else
1015                set_all_masks(l_map, mask);
1016          }
1017          return;
1018       case syntax_element_set:
1019          if(l_map)
1020          {
1021             l_map[0] |= mask_init;
1022             for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1023             {
1024                if(static_cast<re_set*>(state)->_map[
1025                   static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1026                   l_map[i] |= mask;
1027             }
1028          }
1029          return;
1030       case syntax_element_jump:
1031          // take the jump:
1032          state = static_cast<re_alt*>(state)->alt.p;
1033          not_last_jump = -1;
1034          break;
1035       case syntax_element_alt:
1036       case syntax_element_rep:
1037       case syntax_element_dot_rep:
1038       case syntax_element_char_rep:
1039       case syntax_element_short_set_rep:
1040       case syntax_element_long_set_rep:
1041          {
1042             re_alt* rep = static_cast<re_alt*>(state);
1043             if(rep->_map[0] & mask_init)
1044             {
1045                if(l_map)
1046                {
1047                   // copy previous results:
1048                   l_map[0] |= mask_init;
1049                   for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1050                   {
1051                      if(rep->_map[i] & mask_any)
1052                         l_map[i] |= mask;
1053                   }
1054                }
1055                if(pnull)
1056                {
1057                   if(rep->can_be_null & mask_any)
1058                      *pnull |= mask;
1059                }
1060             }
1061             else
1062             {
1063                // we haven't created a startmap for this alternative yet
1064                // so take the union of the two options:
1065                if(is_bad_repeat(state))
1066                {
1067                   set_all_masks(l_map, mask);
1068                   if(pnull)
1069                      *pnull |= mask;
1070                   return;
1071                }
1072                set_bad_repeat(state);
1073                create_startmap(state->next.p, l_map, pnull, mask);
1074                if((state->type == syntax_element_alt)
1075                   || (static_cast<re_repeat*>(state)->min == 0)
1076                   || (not_last_jump == 0))
1077                   create_startmap(rep->alt.p, l_map, pnull, mask);
1078             }
1079          }
1080          return;
1081       case syntax_element_soft_buffer_end:
1082          // match newline or null:
1083          if(l_map)
1084          {
1085             l_map[0] |= mask_init;
1086             l_map['\n'] |= mask;
1087             l_map['\r'] |= mask;
1088          }
1089          if(pnull)
1090             *pnull |= mask;
1091          return;
1092       case syntax_element_endmark:
1093          // need to handle independent subs as a special case:
1094          if(static_cast<re_brace*>(state)->index < 0)
1095          {
1096             // can be null, any character can match:
1097             set_all_masks(l_map, mask);
1098             if(pnull)
1099                *pnull |= mask;
1100             return;
1101          }
1102          else
1103          {
1104             state = state->next.p;
1105             break;
1106          }
1107
1108       case syntax_element_startmark:
1109          // need to handle independent subs as a special case:
1110          if(static_cast<re_brace*>(state)->index == -3)
1111          {
1112             state = state->next.p->next.p;
1113             break;
1114          }
1115          // otherwise fall through:
1116       default:
1117          state = state->next.p;
1118       }
1119       ++not_last_jump;
1120    }
1121 }
1122
1123 template <class charT, class traits>
1124 unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1125 {
1126    //
1127    // find out how the machine starts, so we can optimise the search:
1128    //
1129    while(state)
1130    {
1131       switch(state->type)
1132       {
1133       case syntax_element_startmark:
1134       case syntax_element_endmark:
1135          state = state->next.p;
1136          continue;
1137       case syntax_element_start_line:
1138          return regbase::restart_line;
1139       case syntax_element_word_start:
1140          return regbase::restart_word;
1141       case syntax_element_buffer_start:
1142          return regbase::restart_buf;
1143       case syntax_element_restart_continue:
1144          return regbase::restart_continue;
1145       default:
1146          state = 0;
1147          continue;
1148       }
1149    }
1150    return regbase::restart_any;
1151 }
1152
1153 template <class charT, class traits>
1154 void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1155 {
1156    //
1157    // set mask in all of bits elements,
1158    // if bits[0] has mask_init not set then we can
1159    // optimise this to a call to memset:
1160    //
1161    if(bits)
1162    {
1163       if(bits[0] == 0)
1164          (std::memset)(bits, mask, 1u << CHAR_BIT);
1165       else
1166       {
1167          for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1168             bits[i] |= mask;
1169       }
1170       bits[0] |= mask_init;
1171    }
1172 }
1173
1174 template <class charT, class traits>
1175 bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1176 {
1177    switch(pt->type)
1178    {
1179    case syntax_element_rep:
1180    case syntax_element_dot_rep:
1181    case syntax_element_char_rep:
1182    case syntax_element_short_set_rep:
1183    case syntax_element_long_set_rep:
1184       {
1185          unsigned id = static_cast<re_repeat*>(pt)->id;
1186          if(id > sizeof(m_bad_repeats) * CHAR_BIT)
1187             return true;  // run out of bits, assume we can't traverse this one.
1188          static const boost::uintmax_t one = 1uL;
1189          return m_bad_repeats & (one << id);
1190       }
1191    default:
1192       return false;
1193    }
1194 }
1195
1196 template <class charT, class traits>
1197 void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1198 {
1199    switch(pt->type)
1200    {
1201    case syntax_element_rep:
1202    case syntax_element_dot_rep:
1203    case syntax_element_char_rep:
1204    case syntax_element_short_set_rep:
1205    case syntax_element_long_set_rep:
1206       {
1207          unsigned id = static_cast<re_repeat*>(pt)->id;
1208          static const boost::uintmax_t one = 1uL;
1209          if(id <= sizeof(m_bad_repeats) * CHAR_BIT)
1210             m_bad_repeats |= (one << id);
1211       }
1212    default:
1213       break;
1214    }
1215 }
1216
1217 template <class charT, class traits>
1218 syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1219 {
1220    typedef typename traits::char_class_type mask_type;
1221    if(state->type == syntax_element_rep)
1222    {
1223       // check to see if we are repeating a single state:
1224       if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1225       {
1226          switch(state->next.p->type)
1227          {
1228          case re_detail::syntax_element_wild:
1229             return re_detail::syntax_element_dot_rep;
1230          case re_detail::syntax_element_literal:
1231             return re_detail::syntax_element_char_rep;
1232          case re_detail::syntax_element_set:
1233             return re_detail::syntax_element_short_set_rep;
1234          case re_detail::syntax_element_long_set:
1235             if(static_cast<re_detail::re_set_long<mask_type>*>(state->next.p)->singleton)
1236                return re_detail::syntax_element_long_set_rep;
1237             break;
1238          default:
1239             break;
1240          }
1241       }
1242    }
1243    return state->type;
1244 }
1245
1246 template <class charT, class traits>
1247 void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1248 {
1249    // enumerate our states, and see if we have a leading repeat
1250    // for which failed search restarts can be optimised;
1251    do
1252    {
1253       switch(state->type)
1254       {
1255       case syntax_element_startmark:
1256          if(static_cast<re_brace*>(state)->index >= 0)
1257          {
1258             state = state->next.p;
1259             continue;
1260          }
1261          return;
1262       case syntax_element_endmark:
1263       case syntax_element_start_line:
1264       case syntax_element_end_line:
1265       case syntax_element_word_boundary:
1266       case syntax_element_within_word:
1267       case syntax_element_word_start:
1268       case syntax_element_word_end:
1269       case syntax_element_buffer_start:
1270       case syntax_element_buffer_end:
1271       case syntax_element_restart_continue:
1272          state = state->next.p;
1273          break;
1274       case syntax_element_dot_rep:
1275       case syntax_element_char_rep:
1276       case syntax_element_short_set_rep:
1277       case syntax_element_long_set_rep:
1278          if(this->m_has_backrefs == 0)
1279             static_cast<re_repeat*>(state)->leading = true;
1280          // fall through:
1281       default:
1282          return;
1283       }
1284    }while(state);
1285 }
1286
1287
1288 } // namespace re_detail
1289
1290 } // namespace boost
1291
1292 #ifdef BOOST_HAS_ABI_HEADERS
1293 #  include BOOST_ABI_SUFFIX
1294 #endif
1295
1296 #endif