boost/boost/regex/v4/basic_regex_parser.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_parser.cpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Declares template class basic_regex_parser.
  17   */
  18
  19 #ifndef BOOST_REGEX_V4_BASIC_REGEX_PARSER_HPP
  20 #define BOOST_REGEX_V4_BASIC_REGEX_PARSER_HPP
  21
  22 #ifdef BOOST_MSVC
  23 #pragma warning(push)
  24 #pragma warning(disable: 4103)
  25 #endif
  26 #ifdef BOOST_HAS_ABI_HEADERS
  27 #  include BOOST_ABI_PREFIX
  28 #endif
  29 #ifdef BOOST_MSVC
  30 #pragma warning(pop)
  31 #endif
  32
  33 namespace boost{
  34 namespace re_detail{
  35
  36 #ifdef BOOST_MSVC
  37 #pragma warning(push)
  38 #pragma warning(disable:4244 4800)
  39 #endif
  40
  41 template <class charT, class traits>
  42 class basic_regex_parser : public basic_regex_creator<charT, traits>
  43 {
  44 public:
  45    basic_regex_parser(regex_data<charT, traits>* data);
  46    void parse(const charT* p1, const charT* p2, unsigned flags);
  47    void fail(regex_constants::error_type error_code, std::ptrdiff_t position);
  48    void fail(regex_constants::error_type error_code, std::ptrdiff_t position, std::string message, std::ptrdiff_t start_pos);
  49    void fail(regex_constants::error_type error_code, std::ptrdiff_t position, const std::string& message)
  50    {
  51       fail(error_code, position, message, position);
  52    }
  53
  54    bool parse_all();
  55    bool parse_basic();
  56    bool parse_extended();
  57    bool parse_literal();
  58    bool parse_open_paren();
  59    bool parse_basic_escape();
  60    bool parse_extended_escape();
  61    bool parse_match_any();
  62    bool parse_repeat(std::size_t low = 0, std::size_t high = (std::numeric_limits<std::size_t>::max)());
  63    bool parse_repeat_range(bool isbasic);
  64    bool parse_alt();
  65    bool parse_set();
  66    bool parse_backref();
  67    void parse_set_literal(basic_char_set<charT, traits>& char_set);
  68    bool parse_inner_set(basic_char_set<charT, traits>& char_set);
  69    bool parse_QE();
  70    bool parse_perl_extension();
  71    bool add_emacs_code(bool negate);
  72    bool unwind_alts(std::ptrdiff_t last_paren_start);
  73    digraph<charT> get_next_set_literal(basic_char_set<charT, traits>& char_set);
  74    charT unescape_character();
  75    regex_constants::syntax_option_type parse_options();
  76
  77 private:
  78    typedef bool (basic_regex_parser::*parser_proc_type)();
  79    typedef typename traits::string_type string_type;
  80    typedef typename traits::char_class_type char_class_type;
  81    parser_proc_type           m_parser_proc;    // the main parser to use
  82    const charT*               m_base;           // the start of the string being parsed
  83    const charT*               m_end;            // the end of the string being parsed
  84    const charT*               m_position;       // our current parser position
  85    unsigned                   m_mark_count;     // how many sub-expressions we have
  86    int                        m_mark_reset;     // used to indicate that we're inside a (?|...) block.
  87    unsigned                   m_max_mark;       // largest mark count seen inside a (?|...) block.
  88    std::ptrdiff_t             m_paren_start;    // where the last seen ')' began (where repeats are inserted).
  89    std::ptrdiff_t             m_alt_insert_point; // where to insert the next alternative
  90    bool                       m_has_case_change; // true if somewhere in the current block the case has changed
  91 #if defined(BOOST_MSVC) && defined(_M_IX86)
  92    // This is an ugly warning suppression workaround (for warnings *inside* std::vector
  93    // that can not otherwise be suppressed)...
  94    BOOST_STATIC_ASSERT(sizeof(long) >= sizeof(void*));
  95    std::vector<long>           m_alt_jumps;      // list of alternative in the current scope.
  96 #else
  97    std::vector<std::ptrdiff_t> m_alt_jumps;      // list of alternative in the current scope.
  98 #endif
  99
 100    basic_regex_parser& operator=(const basic_regex_parser&);
 101    basic_regex_parser(const basic_regex_parser&);
 102 };
 103
 104 template <class charT, class traits>
 105 basic_regex_parser<charT, traits>::basic_regex_parser(regex_data<charT, traits>* data)
 106    : basic_regex_creator<charT, traits>(data), m_mark_count(0), m_mark_reset(-1), m_max_mark(0), m_paren_start(0), m_alt_insert_point(0), m_has_case_change(false)
 107 {
 108 }
 109
 110 template <class charT, class traits>
 111 void basic_regex_parser<charT, traits>::parse(const charT* p1, const charT* p2, unsigned l_flags)
 112 {
 113    // pass l_flags on to base class:
 114    this->init(l_flags);
 115    // set up pointers:
 116    m_position = m_base = p1;
 117    m_end = p2;
 118    // empty strings are errors:
 119    if((p1 == p2) &&
 120       (
 121          ((l_flags & regbase::main_option_type) != regbase::perl_syntax_group)
 122          || (l_flags & regbase::no_empty_expressions)
 123       )
 124      )
 125    {
 126       fail(regex_constants::error_empty, 0);
 127       return;
 128    }
 129    // select which parser to use:
 130    switch(l_flags & regbase::main_option_type)
 131    {
 132    case regbase::perl_syntax_group:
 133       {
 134          m_parser_proc = &basic_regex_parser<charT, traits>::parse_extended;
 135          //
 136          // Add a leading paren with index zero to give recursions a target:
 137          //
 138          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_startmark, sizeof(re_brace)));
 139          br->index = 0;
 140          br->icase = this->flags() & regbase::icase;
 141          break;
 142       }
 143    case regbase::basic_syntax_group:
 144       m_parser_proc = &basic_regex_parser<charT, traits>::parse_basic;
 145       break;
 146    case regbase::literal:
 147       m_parser_proc = &basic_regex_parser<charT, traits>::parse_literal;
 148       break;
 149    default:
 150       // Ooops, someone has managed to set more than one of the main option flags,
 151       // so this must be an error:
 152       fail(regex_constants::error_unknown, 0, "An invalid combination of regular expression syntax flags was used.");
 153       return;
 154    }
 155
 156    // parse all our characters:
 157    bool result = parse_all();
 158    //
 159    // Unwind our alternatives:
 160    //
 161    unwind_alts(-1);
 162    // reset l_flags as a global scope (?imsx) may have altered them:
 163    this->flags(l_flags);
 164    // if we haven't gobbled up all the characters then we must
 165    // have had an unexpected ')' :
 166    if(!result)
 167    {
 168       fail(regex_constants::error_paren, ::boost::re_detail::distance(m_base, m_position), "Found a closing ) with no corresponding openening parenthesis.");
 169       return;
 170    }
 171    // if an error has been set then give up now:
 172    if(this->m_pdata->m_status)
 173       return;
 174    // fill in our sub-expression count:
 175    this->m_pdata->m_mark_count = 1 + m_mark_count;
 176    this->finalize(p1, p2);
 177 }
 178
 179 template <class charT, class traits>
 180 void basic_regex_parser<charT, traits>::fail(regex_constants::error_type error_code, std::ptrdiff_t position)
 181 {
 182    // get the error message:
 183    std::string message = this->m_pdata->m_ptraits->error_string(error_code);
 184    fail(error_code, position, message);
 185 }
 186
 187 template <class charT, class traits>
 188 void basic_regex_parser<charT, traits>::fail(regex_constants::error_type error_code, std::ptrdiff_t position, std::string message, std::ptrdiff_t start_pos)
 189 {
 190    if(0 == this->m_pdata->m_status) // update the error code if not already set
 191       this->m_pdata->m_status = error_code;
 192    m_position = m_end; // don't bother parsing anything else
 193
 194    //
 195    // Augment error message with the regular expression text:
 196    //
 197    if(start_pos == position)
 198       start_pos = (std::max)(static_cast<std::ptrdiff_t>(0), position - static_cast<std::ptrdiff_t>(10));
 199    std::ptrdiff_t end_pos = (std::min)(position + static_cast<std::ptrdiff_t>(10), static_cast<std::ptrdiff_t>(m_end - m_base));
 200    if(error_code != regex_constants::error_empty)
 201    {
 202       if((start_pos != 0) || (end_pos != (m_end - m_base)))
 203          message += "  The error occured while parsing the regular expression fragment: '";
 204       else
 205          message += "  The error occured while parsing the regular expression: '";
 206       if(start_pos != end_pos)
 207       {
 208          message += std::string(m_base + start_pos, m_base + position);
 209          message += ">>>HERE>>>";
 210          message += std::string(m_base + position, m_base + end_pos);
 211       }
 212       message += "'.";
 213    }
 214
 215 #ifndef BOOST_NO_EXCEPTIONS
 216    if(0 == (this->flags() & regex_constants::no_except))
 217    {
 218       boost::regex_error e(message, error_code, position);
 219       e.raise();
 220    }
 221 #else
 222    (void)position; // suppress warnings.
 223 #endif
 224 }
 225
 226 template <class charT, class traits>
 227 bool basic_regex_parser<charT, traits>::parse_all()
 228 {
 229    bool result = true;
 230    while(result && (m_position != m_end))
 231    {
 232       result = (this->*m_parser_proc)();
 233    }
 234    return result;
 235 }
 236
 237 #ifdef BOOST_MSVC
 238 #pragma warning(push)
 239 #pragma warning(disable:4702)
 240 #endif
 241 template <class charT, class traits>
 242 bool basic_regex_parser<charT, traits>::parse_basic()
 243 {
 244    switch(this->m_traits.syntax_type(*m_position))
 245    {
 246    case regex_constants::syntax_escape:
 247       return parse_basic_escape();
 248    case regex_constants::syntax_dot:
 249       return parse_match_any();
 250    case regex_constants::syntax_caret:
 251       ++m_position;
 252       this->append_state(syntax_element_start_line);
 253       break;
 254    case regex_constants::syntax_dollar:
 255       ++m_position;
 256       this->append_state(syntax_element_end_line);
 257       break;
 258    case regex_constants::syntax_star:
 259       if(!(this->m_last_state) || (this->m_last_state->type == syntax_element_start_line))
 260          return parse_literal();
 261       else
 262       {
 263          ++m_position;
 264          return parse_repeat();
 265       }
 266    case regex_constants::syntax_plus:
 267       if(!(this->m_last_state) || (this->m_last_state->type == syntax_element_start_line) || !(this->flags() & regbase::emacs_ex))
 268          return parse_literal();
 269       else
 270       {
 271          ++m_position;
 272          return parse_repeat(1);
 273       }
 274    case regex_constants::syntax_question:
 275       if(!(this->m_last_state) || (this->m_last_state->type == syntax_element_start_line) || !(this->flags() & regbase::emacs_ex))
 276          return parse_literal();
 277       else
 278       {
 279          ++m_position;
 280          return parse_repeat(0, 1);
 281       }
 282    case regex_constants::syntax_open_set:
 283       return parse_set();
 284    case regex_constants::syntax_newline:
 285       if(this->flags() & regbase::newline_alt)
 286          return parse_alt();
 287       else
 288          return parse_literal();
 289    default:
 290       return parse_literal();
 291    }
 292    return true;
 293 }
 294
 295 template <class charT, class traits>
 296 bool basic_regex_parser<charT, traits>::parse_extended()
 297 {
 298    bool result = true;
 299    switch(this->m_traits.syntax_type(*m_position))
 300    {
 301    case regex_constants::syntax_open_mark:
 302       return parse_open_paren();
 303    case regex_constants::syntax_close_mark:
 304       return false;
 305    case regex_constants::syntax_escape:
 306       return parse_extended_escape();
 307    case regex_constants::syntax_dot:
 308       return parse_match_any();
 309    case regex_constants::syntax_caret:
 310       ++m_position;
 311       this->append_state(
 312          (this->flags() & regex_constants::no_mod_m ? syntax_element_buffer_start : syntax_element_start_line));
 313       break;
 314    case regex_constants::syntax_dollar:
 315       ++m_position;
 316       this->append_state(
 317          (this->flags() & regex_constants::no_mod_m ? syntax_element_buffer_end : syntax_element_end_line));
 318       break;
 319    case regex_constants::syntax_star:
 320       if(m_position == this->m_base)
 321       {
 322          fail(regex_constants::error_badrepeat, 0, "The repeat operator \"*\" cannot start a regular expression.");
 323          return false;
 324       }
 325       ++m_position;
 326       return parse_repeat();
 327    case regex_constants::syntax_question:
 328       if(m_position == this->m_base)
 329       {
 330          fail(regex_constants::error_badrepeat, 0, "The repeat operator \"?\" cannot start a regular expression.");
 331          return false;
 332       }
 333       ++m_position;
 334       return parse_repeat(0,1);
 335    case regex_constants::syntax_plus:
 336       if(m_position == this->m_base)
 337       {
 338          fail(regex_constants::error_badrepeat, 0, "The repeat operator \"+\" cannot start a regular expression.");
 339          return false;
 340       }
 341       ++m_position;
 342       return parse_repeat(1);
 343    case regex_constants::syntax_open_brace:
 344       ++m_position;
 345       return parse_repeat_range(false);
 346    case regex_constants::syntax_close_brace:
 347       fail(regex_constants::error_brace, this->m_position - this->m_base, "Found a closing repetition operator } with no corresponding {.");
 348       return false;
 349    case regex_constants::syntax_or:
 350       return parse_alt();
 351    case regex_constants::syntax_open_set:
 352       return parse_set();
 353    case regex_constants::syntax_newline:
 354       if(this->flags() & regbase::newline_alt)
 355          return parse_alt();
 356       else
 357          return parse_literal();
 358    case regex_constants::syntax_hash:
 359       //
 360       // If we have a mod_x flag set, then skip until
 361       // we get to a newline character:
 362       //
 363       if((this->flags()
 364          & (regbase::no_perl_ex|regbase::mod_x))
 365          == regbase::mod_x)
 366       {
 367          while((m_position != m_end) && !is_separator(*m_position++)){}
 368          return true;
 369       }
 370       // Otherwise fall through:
 371    default:
 372       result = parse_literal();
 373       break;
 374    }
 375    return result;
 376 }
 377 #ifdef BOOST_MSVC
 378 #pragma warning(pop)
 379 #endif
 380
 381 template <class charT, class traits>
 382 bool basic_regex_parser<charT, traits>::parse_literal()
 383 {
 384    // append this as a literal provided it's not a space character
 385    // or the perl option regbase::mod_x is not set:
 386    if(
 387       ((this->flags()
 388          & (regbase::main_option_type|regbase::mod_x|regbase::no_perl_ex))
 389             != regbase::mod_x)
 390       || !this->m_traits.isctype(*m_position, this->m_mask_space))
 391          this->append_literal(*m_position);
 392    ++m_position;
 393    return true;
 394 }
 395
 396 template <class charT, class traits>
 397 bool basic_regex_parser<charT, traits>::parse_open_paren()
 398 {
 399    //
 400    // skip the '(' and error check:
 401    //
 402    if(++m_position == m_end)
 403    {
 404       fail(regex_constants::error_paren, m_position - m_base);
 405       return false;
 406    }
 407    //
 408    // begin by checking for a perl-style (?...) extension:
 409    //
 410    if(
 411          ((this->flags() & (regbase::main_option_type | regbase::no_perl_ex)) == 0)
 412          || ((this->flags() & (regbase::main_option_type | regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
 413      )
 414    {
 415       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_question)
 416          return parse_perl_extension();
 417    }
 418    //
 419    // update our mark count, and append the required state:
 420    //
 421    unsigned markid = 0;
 422    if(0 == (this->flags() & regbase::nosubs))
 423    {
 424       markid = ++m_mark_count;
 425 #ifndef BOOST_NO_STD_DISTANCE
 426       if(this->flags() & regbase::save_subexpression_location)
 427          this->m_pdata->m_subs.push_back(std::pair<std::size_t, std::size_t>(std::distance(m_base, m_position) - 1, 0));
 428 #else
 429       if(this->flags() & regbase::save_subexpression_location)
 430          this->m_pdata->m_subs.push_back(std::pair<std::size_t, std::size_t>((m_position - m_base) - 1, 0));
 431 #endif
 432    }
 433    re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_startmark, sizeof(re_brace)));
 434    pb->index = markid;
 435    pb->icase = this->flags() & regbase::icase;
 436    std::ptrdiff_t last_paren_start = this->getoffset(pb);
 437    // back up insertion point for alternations, and set new point:
 438    std::ptrdiff_t last_alt_point = m_alt_insert_point;
 439    this->m_pdata->m_data.align();
 440    m_alt_insert_point = this->m_pdata->m_data.size();
 441    //
 442    // back up the current flags in case we have a nested (?imsx) group:
 443    //
 444    regex_constants::syntax_option_type opts = this->flags();
 445    bool old_case_change = m_has_case_change;
 446    m_has_case_change = false; // no changes to this scope as yet...
 447    //
 448    // Back up branch reset data in case we have a nested (?|...)
 449    //
 450    int mark_reset = m_mark_reset;
 451    m_mark_reset = -1;
 452    //
 453    // now recursively add more states, this will terminate when we get to a
 454    // matching ')' :
 455    //
 456    parse_all();
 457    //
 458    // Unwind pushed alternatives:
 459    //
 460    if(0 == unwind_alts(last_paren_start))
 461       return false;
 462    //
 463    // restore flags:
 464    //
 465    if(m_has_case_change)
 466    {
 467       // the case has changed in one or more of the alternatives
 468       // within the scoped (...) block: we have to add a state
 469       // to reset the case sensitivity:
 470       static_cast<re_case*>(
 471          this->append_state(syntax_element_toggle_case, sizeof(re_case))
 472          )->icase = opts & regbase::icase;
 473    }
 474    this->flags(opts);
 475    m_has_case_change = old_case_change;
 476    //
 477    // restore branch reset:
 478    //
 479    m_mark_reset = mark_reset;
 480    //
 481    // we either have a ')' or we have run out of characters prematurely:
 482    //
 483    if(m_position == m_end)
 484    {
 485       this->fail(regex_constants::error_paren, ::boost::re_detail::distance(m_base, m_end));
 486       return false;
 487    }
 488    BOOST_ASSERT(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_mark);
 489 #ifndef BOOST_NO_STD_DISTANCE
 490    if(markid && (this->flags() & regbase::save_subexpression_location))
 491       this->m_pdata->m_subs.at(markid - 1).second = std::distance(m_base, m_position);
 492 #else
 493    if(markid && (this->flags() & regbase::save_subexpression_location))
 494       this->m_pdata->m_subs.at(markid - 1).second = (m_position - m_base);
 495 #endif
 496    ++m_position;
 497    //
 498    // append closing parenthesis state:
 499    //
 500    pb = static_cast<re_brace*>(this->append_state(syntax_element_endmark, sizeof(re_brace)));
 501    pb->index = markid;
 502    pb->icase = this->flags() & regbase::icase;
 503    this->m_paren_start = last_paren_start;
 504    //
 505    // restore the alternate insertion point:
 506    //
 507    this->m_alt_insert_point = last_alt_point;
 508    //
 509    // allow backrefs to this mark:
 510    //
 511    if((markid > 0) && (markid < sizeof(unsigned) * CHAR_BIT))
 512       this->m_backrefs |= 1u << (markid - 1);
 513
 514    return true;
 515 }
 516
 517 template <class charT, class traits>
 518 bool basic_regex_parser<charT, traits>::parse_basic_escape()
 519 {
 520    ++m_position;
 521    bool result = true;
 522    switch(this->m_traits.escape_syntax_type(*m_position))
 523    {
 524    case regex_constants::syntax_open_mark:
 525       return parse_open_paren();
 526    case regex_constants::syntax_close_mark:
 527       return false;
 528    case regex_constants::syntax_plus:
 529       if(this->flags() & regex_constants::bk_plus_qm)
 530       {
 531          ++m_position;
 532          return parse_repeat(1);
 533       }
 534       else
 535          return parse_literal();
 536    case regex_constants::syntax_question:
 537       if(this->flags() & regex_constants::bk_plus_qm)
 538       {
 539          ++m_position;
 540          return parse_repeat(0, 1);
 541       }
 542       else
 543          return parse_literal();
 544    case regex_constants::syntax_open_brace:
 545       if(this->flags() & regbase::no_intervals)
 546          return parse_literal();
 547       ++m_position;
 548       return parse_repeat_range(true);
 549    case regex_constants::syntax_close_brace:
 550       if(this->flags() & regbase::no_intervals)
 551          return parse_literal();
 552       fail(regex_constants::error_brace, this->m_position - this->m_base, "Found a closing repetition operator } with no corresponding {.");
 553       return false;
 554    case regex_constants::syntax_or:
 555       if(this->flags() & regbase::bk_vbar)
 556          return parse_alt();
 557       else
 558          result = parse_literal();
 559       break;
 560    case regex_constants::syntax_digit:
 561       return parse_backref();
 562    case regex_constants::escape_type_start_buffer:
 563       if(this->flags() & regbase::emacs_ex)
 564       {
 565          ++m_position;
 566          this->append_state(syntax_element_buffer_start);
 567       }
 568       else
 569          result = parse_literal();
 570       break;
 571    case regex_constants::escape_type_end_buffer:
 572       if(this->flags() & regbase::emacs_ex)
 573       {
 574          ++m_position;
 575          this->append_state(syntax_element_buffer_end);
 576       }
 577       else
 578          result = parse_literal();
 579       break;
 580    case regex_constants::escape_type_word_assert:
 581       if(this->flags() & regbase::emacs_ex)
 582       {
 583          ++m_position;
 584          this->append_state(syntax_element_word_boundary);
 585       }
 586       else
 587          result = parse_literal();
 588       break;
 589    case regex_constants::escape_type_not_word_assert:
 590       if(this->flags() & regbase::emacs_ex)
 591       {
 592          ++m_position;
 593          this->append_state(syntax_element_within_word);
 594       }
 595       else
 596          result = parse_literal();
 597       break;
 598    case regex_constants::escape_type_left_word:
 599       if(this->flags() & regbase::emacs_ex)
 600       {
 601          ++m_position;
 602          this->append_state(syntax_element_word_start);
 603       }
 604       else
 605          result = parse_literal();
 606       break;
 607    case regex_constants::escape_type_right_word:
 608       if(this->flags() & regbase::emacs_ex)
 609       {
 610          ++m_position;
 611          this->append_state(syntax_element_word_end);
 612       }
 613       else
 614          result = parse_literal();
 615       break;
 616    default:
 617       if(this->flags() & regbase::emacs_ex)
 618       {
 619          bool negate = true;
 620          switch(*m_position)
 621          {
 622          case 'w':
 623             negate = false;
 624             // fall through:
 625          case 'W':
 626             {
 627             basic_char_set<charT, traits> char_set;
 628             if(negate)
 629                char_set.negate();
 630             char_set.add_class(this->m_word_mask);
 631             if(0 == this->append_set(char_set))
 632             {
 633                fail(regex_constants::error_ctype, m_position - m_base);
 634                return false;
 635             }
 636             ++m_position;
 637             return true;
 638             }
 639          case 's':
 640             negate = false;
 641             // fall through:
 642          case 'S':
 643             return add_emacs_code(negate);
 644          case 'c':
 645          case 'C':
 646             // not supported yet:
 647             fail(regex_constants::error_escape, m_position - m_base, "The \\c and \\C escape sequences are not supported by POSIX basic regular expressions: try the Perl syntax instead.");
 648             return false;
 649          default:
 650             break;
 651          }
 652       }
 653       result = parse_literal();
 654       break;
 655    }
 656    return result;
 657 }
 658
 659 template <class charT, class traits>
 660 bool basic_regex_parser<charT, traits>::parse_extended_escape()
 661 {
 662    ++m_position;
 663    bool negate = false; // in case this is a character class escape: \w \d etc
 664    switch(this->m_traits.escape_syntax_type(*m_position))
 665    {
 666    case regex_constants::escape_type_not_class:
 667       negate = true;
 668       // fall through:
 669    case regex_constants::escape_type_class:
 670       {
 671 escape_type_class_jump:
 672          typedef typename traits::char_class_type mask_type;
 673          mask_type m = this->m_traits.lookup_classname(m_position, m_position+1);
 674          if(m != 0)
 675          {
 676             basic_char_set<charT, traits> char_set;
 677             if(negate)
 678                char_set.negate();
 679             char_set.add_class(m);
 680             if(0 == this->append_set(char_set))
 681             {
 682                fail(regex_constants::error_ctype, m_position - m_base);
 683                return false;
 684             }
 685             ++m_position;
 686             return true;
 687          }
 688          //
 689          // not a class, just a regular unknown escape:
 690          //
 691          this->append_literal(unescape_character());
 692          break;
 693       }
 694    case regex_constants::syntax_digit:
 695       return parse_backref();
 696    case regex_constants::escape_type_left_word:
 697       ++m_position;
 698       this->append_state(syntax_element_word_start);
 699       break;
 700    case regex_constants::escape_type_right_word:
 701       ++m_position;
 702       this->append_state(syntax_element_word_end);
 703       break;
 704    case regex_constants::escape_type_start_buffer:
 705       ++m_position;
 706       this->append_state(syntax_element_buffer_start);
 707       break;
 708    case regex_constants::escape_type_end_buffer:
 709       ++m_position;
 710       this->append_state(syntax_element_buffer_end);
 711       break;
 712    case regex_constants::escape_type_word_assert:
 713       ++m_position;
 714       this->append_state(syntax_element_word_boundary);
 715       break;
 716    case regex_constants::escape_type_not_word_assert:
 717       ++m_position;
 718       this->append_state(syntax_element_within_word);
 719       break;
 720    case regex_constants::escape_type_Z:
 721       ++m_position;
 722       this->append_state(syntax_element_soft_buffer_end);
 723       break;
 724    case regex_constants::escape_type_Q:
 725       return parse_QE();
 726    case regex_constants::escape_type_C:
 727       return parse_match_any();
 728    case regex_constants::escape_type_X:
 729       ++m_position;
 730       this->append_state(syntax_element_combining);
 731       break;
 732    case regex_constants::escape_type_G:
 733       ++m_position;
 734       this->append_state(syntax_element_restart_continue);
 735       break;
 736    case regex_constants::escape_type_not_property:
 737       negate = true;
 738       // fall through:
 739    case regex_constants::escape_type_property:
 740       {
 741          ++m_position;
 742          char_class_type m;
 743          if(m_position == m_end)
 744          {
 745             fail(regex_constants::error_escape, m_position - m_base, "Incomplete property escape found.");
 746             return false;
 747          }
 748          // maybe have \p{ddd}
 749          if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_open_brace)
 750          {
 751             const charT* base = m_position;
 752             // skip forward until we find enclosing brace:
 753             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_brace))
 754                ++m_position;
 755             if(m_position == m_end)
 756             {
 757                fail(regex_constants::error_escape, m_position - m_base, "Closing } missing from property escape sequence.");
 758                return false;
 759             }
 760             m = this->m_traits.lookup_classname(++base, m_position++);
 761          }
 762          else
 763          {
 764             m = this->m_traits.lookup_classname(m_position, m_position+1);
 765             ++m_position;
 766          }
 767          if(m != 0)
 768          {
 769             basic_char_set<charT, traits> char_set;
 770             if(negate)
 771                char_set.negate();
 772             char_set.add_class(m);
 773             if(0 == this->append_set(char_set))
 774             {
 775                fail(regex_constants::error_ctype, m_position - m_base);
 776                return false;
 777             }
 778             return true;
 779          }
 780          fail(regex_constants::error_ctype, m_position - m_base, "Escape sequence was neither a valid property nor a valid character class name.");
 781          return false;
 782       }
 783    case regex_constants::escape_type_reset_start_mark:
 784       if(0 == (this->flags() & (regbase::main_option_type | regbase::no_perl_ex)))
 785       {
 786          re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_startmark, sizeof(re_brace)));
 787          pb->index = -5;
 788          pb->icase = this->flags() & regbase::icase;
 789          this->m_pdata->m_data.align();
 790          ++m_position;
 791          return true;
 792       }
 793       goto escape_type_class_jump;
 794    case regex_constants::escape_type_line_ending:
 795       if(0 == (this->flags() & (regbase::main_option_type | regbase::no_perl_ex)))
 796       {
 797          const charT* e = get_escape_R_string<charT>();
 798          const charT* old_position = m_position;
 799          const charT* old_end = m_end;
 800          const charT* old_base = m_base;
 801          m_position = e;
 802          m_base = e;
 803          m_end = e + traits::length(e);
 804          bool r = parse_all();
 805          m_position = ++old_position;
 806          m_end = old_end;
 807          m_base = old_base;
 808          return r;
 809       }
 810       goto escape_type_class_jump;
 811    case regex_constants::escape_type_extended_backref:
 812       if(0 == (this->flags() & (regbase::main_option_type | regbase::no_perl_ex)))
 813       {
 814          bool have_brace = false;
 815          bool negative = false;
 816          static const char* incomplete_message = "Incomplete \\g escape found.";
 817          if(++m_position == m_end)
 818          {
 819             fail(regex_constants::error_escape, m_position - m_base, incomplete_message);
 820             return false;
 821          }
 822          // maybe have \g{ddd}
 823          regex_constants::syntax_type syn = this->m_traits.syntax_type(*m_position);
 824          regex_constants::syntax_type syn_end = 0;
 825          if((syn == regex_constants::syntax_open_brace)
 826             || (syn == regex_constants::escape_type_left_word)
 827             || (syn == regex_constants::escape_type_end_buffer))
 828          {
 829             if(++m_position == m_end)
 830             {
 831                fail(regex_constants::error_escape, m_position - m_base, incomplete_message);
 832                return false;
 833             }
 834             have_brace = true;
 835             switch(syn)
 836             {
 837             case regex_constants::syntax_open_brace:
 838                syn_end = regex_constants::syntax_close_brace;
 839                break;
 840             case regex_constants::escape_type_left_word:
 841                syn_end = regex_constants::escape_type_right_word;
 842                break;
 843             default:
 844                syn_end = regex_constants::escape_type_end_buffer;
 845                break;
 846             }
 847          }
 848          negative = (*m_position == static_cast<charT>('-'));
 849          if((negative) && (++m_position == m_end))
 850          {
 851             fail(regex_constants::error_escape, m_position - m_base, incomplete_message);
 852             return false;
 853          }
 854          const charT* pc = m_position;
 855          int i = this->m_traits.toi(pc, m_end, 10);
 856          if((i < 0) && syn_end)
 857          {
 858             // Check for a named capture, get the leftmost one if there is more than one:
 859             const charT* base = m_position;
 860             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != syn_end))
 861             {
 862                ++m_position;
 863             }
 864             i = hash_value_from_capture_name(base, m_position);
 865             pc = m_position;
 866          }
 867          if(negative)
 868             i = 1 + m_mark_count - i;
 869          if(((i > 0) && (this->m_backrefs & (1u << (i-1)))) || ((i > 10000) && (this->m_pdata->get_id(i) > 0) && (this->m_backrefs & (1u << (this->m_pdata->get_id(i)-1)))))
 870          {
 871             m_position = pc;
 872             re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_backref, sizeof(re_brace)));
 873             pb->index = i;
 874             pb->icase = this->flags() & regbase::icase;
 875          }
 876          else
 877          {
 878             fail(regex_constants::error_backref, m_position - m_base);
 879             return false;
 880          }
 881          m_position = pc;
 882          if(have_brace)
 883          {
 884             if((m_position == m_end) || (this->m_traits.syntax_type(*m_position) != syn_end))
 885             {
 886                fail(regex_constants::error_escape, m_position - m_base, incomplete_message);
 887                return false;
 888             }
 889             ++m_position;
 890          }
 891          return true;
 892       }
 893       goto escape_type_class_jump;
 894    case regex_constants::escape_type_control_v:
 895       if(0 == (this->flags() & (regbase::main_option_type | regbase::no_perl_ex)))
 896          goto escape_type_class_jump;
 897       // fallthrough:
 898    default:
 899       this->append_literal(unescape_character());
 900       break;
 901    }
 902    return true;
 903 }
 904
 905 template <class charT, class traits>
 906 bool basic_regex_parser<charT, traits>::parse_match_any()
 907 {
 908    //
 909    // we have a '.' that can match any character:
 910    //
 911    ++m_position;
 912    static_cast<re_dot*>(
 913       this->append_state(syntax_element_wild, sizeof(re_dot))
 914       )->mask = static_cast<unsigned char>(this->flags() & regbase::no_mod_s
 915       ? re_detail::force_not_newline
 916          : this->flags() & regbase::mod_s ?
 917             re_detail::force_newline : re_detail::dont_care);
 918    return true;
 919 }
 920
 921 template <class charT, class traits>
 922 bool basic_regex_parser<charT, traits>::parse_repeat(std::size_t low, std::size_t high)
 923 {
 924    bool greedy = true;
 925    bool pocessive = false;
 926    std::size_t insert_point;
 927    //
 928    // when we get to here we may have a non-greedy ? mark still to come:
 929    //
 930    if((m_position != m_end)
 931       && (
 932             (0 == (this->flags() & (regbase::main_option_type | regbase::no_perl_ex)))
 933             || ((regbase::basic_syntax_group|regbase::emacs_ex) == (this->flags() & (regbase::main_option_type | regbase::emacs_ex)))
 934          )
 935       )
 936    {
 937       // OK we have a perl or emacs regex, check for a '?':
 938       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_question)
 939       {
 940          greedy = false;
 941          ++m_position;
 942       }
 943       // for perl regexes only check for pocessive ++ repeats.
 944       if((0 == (this->flags() & regbase::main_option_type))
 945          && (this->m_traits.syntax_type(*m_position) == regex_constants::syntax_plus))
 946       {
 947          pocessive = true;
 948          ++m_position;
 949       }
 950    }
 951    if(0 == this->m_last_state)
 952    {
 953       fail(regex_constants::error_badrepeat, ::boost::re_detail::distance(m_base, m_position), "Nothing to repeat.");
 954       return false;
 955    }
 956    if(this->m_last_state->type == syntax_element_endmark)
 957    {
 958       // insert a repeat before the '(' matching the last ')':
 959       insert_point = this->m_paren_start;
 960    }
 961    else if((this->m_last_state->type == syntax_element_literal) && (static_cast<re_literal*>(this->m_last_state)->length > 1))
 962    {
 963       // the last state was a literal with more than one character, split it in two:
 964       re_literal* lit = static_cast<re_literal*>(this->m_last_state);
 965       charT c = (static_cast<charT*>(static_cast<void*>(lit+1)))[lit->length - 1];
 966       --(lit->length);
 967       // now append new state:
 968       lit = static_cast<re_literal*>(this->append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
 969       lit->length = 1;
 970       (static_cast<charT*>(static_cast<void*>(lit+1)))[0] = c;
 971       insert_point = this->getoffset(this->m_last_state);
 972    }
 973    else
 974    {
 975       // repeat the last state whatever it was, need to add some error checking here:
 976       switch(this->m_last_state->type)
 977       {
 978       case syntax_element_start_line:
 979       case syntax_element_end_line:
 980       case syntax_element_word_boundary:
 981       case syntax_element_within_word:
 982       case syntax_element_word_start:
 983       case syntax_element_word_end:
 984       case syntax_element_buffer_start:
 985       case syntax_element_buffer_end:
 986       case syntax_element_alt:
 987       case syntax_element_soft_buffer_end:
 988       case syntax_element_restart_continue:
 989       case syntax_element_jump:
 990       case syntax_element_startmark:
 991       case syntax_element_backstep:
 992          // can't legally repeat any of the above:
 993          fail(regex_constants::error_badrepeat, m_position - m_base);
 994          return false;
 995       default:
 996          // do nothing...
 997          break;
 998       }
 999       insert_point = this->getoffset(this->m_last_state);
1000    }
1001    //
1002    // OK we now know what to repeat, so insert the repeat around it:
1003    //
1004    re_repeat* rep = static_cast<re_repeat*>(this->insert_state(insert_point, syntax_element_rep, re_repeater_size));
1005    rep->min = low;
1006    rep->max = high;
1007    rep->greedy = greedy;
1008    rep->leading = false;
1009    // store our repeater position for later:
1010    std::ptrdiff_t rep_off = this->getoffset(rep);
1011    // and append a back jump to the repeat:
1012    re_jump* jmp = static_cast<re_jump*>(this->append_state(syntax_element_jump, sizeof(re_jump)));
1013    jmp->alt.i = rep_off - this->getoffset(jmp);
1014    this->m_pdata->m_data.align();
1015    // now fill in the alt jump for the repeat:
1016    rep = static_cast<re_repeat*>(this->getaddress(rep_off));
1017    rep->alt.i = this->m_pdata->m_data.size() - rep_off;
1018    //
1019    // If the repeat is pocessive then bracket the repeat with a (?>...)
1020    // independent sub-expression construct:
1021    //
1022    if(pocessive)
1023    {
1024       if(m_position != m_end)
1025       {
1026          //
1027          // Check for illegal following quantifier, we have to do this here, because
1028          // the extra states we insert below circumvents are usual error checking :-(
1029          //
1030          switch(this->m_traits.syntax_type(*m_position))
1031          {
1032          case regex_constants::syntax_star:
1033          case regex_constants::syntax_plus:
1034          case regex_constants::syntax_question:
1035             fail(regex_constants::error_badrepeat, m_position - m_base);
1036             return false;
1037          }
1038       }
1039       re_brace* pb = static_cast<re_brace*>(this->insert_state(insert_point, syntax_element_startmark, sizeof(re_brace)));
1040       pb->index = -3;
1041       pb->icase = this->flags() & regbase::icase;
1042       jmp = static_cast<re_jump*>(this->insert_state(insert_point + sizeof(re_brace), syntax_element_jump, sizeof(re_jump)));
1043       this->m_pdata->m_data.align();
1044       jmp->alt.i = this->m_pdata->m_data.size() - this->getoffset(jmp);
1045       pb = static_cast<re_brace*>(this->append_state(syntax_element_endmark, sizeof(re_brace)));
1046       pb->index = -3;
1047       pb->icase = this->flags() & regbase::icase;
1048    }
1049    return true;
1050 }
1051
1052 template <class charT, class traits>
1053 bool basic_regex_parser<charT, traits>::parse_repeat_range(bool isbasic)
1054 {
1055    static const char* incomplete_message = "Missing } in quantified repetition.";
1056    //
1057    // parse a repeat-range:
1058    //
1059    std::size_t min, max;
1060    int v;
1061    // skip whitespace:
1062    while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1063       ++m_position;
1064    // fail if at end:
1065    if(this->m_position == this->m_end)
1066    {
1067       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1068       return false;
1069    }
1070    // get min:
1071    v = this->m_traits.toi(m_position, m_end, 10);
1072    // skip whitespace:
1073    while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1074       ++m_position;
1075    if(v < 0)
1076    {
1077       fail(regex_constants::error_badbrace, this->m_position - this->m_base);
1078       return false;
1079    }
1080    else if(this->m_position == this->m_end)
1081    {
1082       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1083       return false;
1084    }
1085    min = v;
1086    // see if we have a comma:
1087    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_comma)
1088    {
1089       // move on and error check:
1090       ++m_position;
1091       // skip whitespace:
1092       while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1093          ++m_position;
1094       if(this->m_position == this->m_end)
1095       {
1096          fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1097          return false;
1098       }
1099       // get the value if any:
1100       v = this->m_traits.toi(m_position, m_end, 10);
1101       max = (v >= 0) ? v : (std::numeric_limits<std::size_t>::max)();
1102    }
1103    else
1104    {
1105       // no comma, max = min:
1106       max = min;
1107    }
1108    // skip whitespace:
1109    while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1110       ++m_position;
1111    // OK now check trailing }:
1112    if(this->m_position == this->m_end)
1113    {
1114       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1115       return false;
1116    }
1117    if(isbasic)
1118    {
1119       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_escape)
1120       {
1121          ++m_position;
1122          if(this->m_position == this->m_end)
1123          {
1124             fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1125             return false;
1126          }
1127       }
1128       else
1129       {
1130          fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1131          return false;
1132       }
1133    }
1134    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_brace)
1135       ++m_position;
1136    else
1137    {
1138       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1139       return false;
1140    }
1141    //
1142    // finally go and add the repeat, unless error:
1143    //
1144    if(min > max)
1145    {
1146       // Backtrack to error location:
1147       m_position -= 2;
1148       while(this->m_traits.isctype(*m_position, this->m_word_mask)) --m_position;
1149          ++m_position;
1150       fail(regex_constants::error_badbrace, m_position - m_base);
1151       return false;
1152    }
1153    return parse_repeat(min, max);
1154 }
1155
1156 template <class charT, class traits>
1157 bool basic_regex_parser<charT, traits>::parse_alt()
1158 {
1159    //
1160    // error check: if there have been no previous states,
1161    // or if the last state was a '(' then error:
1162    //
1163    if(
1164       ((this->m_last_state == 0) || (this->m_last_state->type == syntax_element_startmark))
1165       &&
1166       !(
1167          ((this->flags() & regbase::main_option_type) == regbase::perl_syntax_group)
1168            &&
1169          ((this->flags() & regbase::no_empty_expressions) == 0)
1170         )
1171       )
1172    {
1173       fail(regex_constants::error_empty, this->m_position - this->m_base, "A regular expression can start with the alternation operator |.");
1174       return false;
1175    }
1176    //
1177    // Reset mark count if required:
1178    //
1179    if(m_max_mark < m_mark_count)
1180       m_max_mark = m_mark_count;
1181    if(m_mark_reset >= 0)
1182       m_mark_count = m_mark_reset;
1183
1184    ++m_position;
1185    //
1186    // we need to append a trailing jump:
1187    //
1188    re_syntax_base* pj = this->append_state(re_detail::syntax_element_jump, sizeof(re_jump));
1189    std::ptrdiff_t jump_offset = this->getoffset(pj);
1190    //
1191    // now insert the alternative:
1192    //
1193    re_alt* palt = static_cast<re_alt*>(this->insert_state(this->m_alt_insert_point, syntax_element_alt, re_alt_size));
1194    jump_offset += re_alt_size;
1195    this->m_pdata->m_data.align();
1196    palt->alt.i = this->m_pdata->m_data.size() - this->getoffset(palt);
1197    //
1198    // update m_alt_insert_point so that the next alternate gets
1199    // inserted at the start of the second of the two we've just created:
1200    //
1201    this->m_alt_insert_point = this->m_pdata->m_data.size();
1202    //
1203    // the start of this alternative must have a case changes state
1204    // if the current block has messed around with case changes:
1205    //
1206    if(m_has_case_change)
1207    {
1208       static_cast<re_case*>(
1209          this->append_state(syntax_element_toggle_case, sizeof(re_case))
1210          )->icase = this->m_icase;
1211    }
1212    //
1213    // push the alternative onto our stack, a recursive
1214    // implementation here is easier to understand (and faster
1215    // as it happens), but causes all kinds of stack overflow problems
1216    // on programs with small stacks (COM+).
1217    //
1218    m_alt_jumps.push_back(jump_offset);
1219    return true;
1220 }
1221
1222 template <class charT, class traits>
1223 bool basic_regex_parser<charT, traits>::parse_set()
1224 {
1225    static const char* incomplete_message = "Character set declaration starting with [ terminated prematurely - either no ] was found or the set had no content.";
1226    ++m_position;
1227    if(m_position == m_end)
1228    {
1229       fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1230       return false;
1231    }
1232    basic_char_set<charT, traits> char_set;
1233
1234    const charT* base = m_position;  // where the '[' was
1235    const charT* item_base = m_position;  // where the '[' or '^' was
1236
1237    while(m_position != m_end)
1238    {
1239       switch(this->m_traits.syntax_type(*m_position))
1240       {
1241       case regex_constants::syntax_caret:
1242          if(m_position == base)
1243          {
1244             char_set.negate();
1245             ++m_position;
1246             item_base = m_position;
1247          }
1248          else
1249             parse_set_literal(char_set);
1250          break;
1251       case regex_constants::syntax_close_set:
1252          if(m_position == item_base)
1253          {
1254             parse_set_literal(char_set);
1255             break;
1256          }
1257          else
1258          {
1259             ++m_position;
1260             if(0 == this->append_set(char_set))
1261             {
1262                fail(regex_constants::error_ctype, m_position - m_base);
1263                return false;
1264             }
1265          }
1266          return true;
1267       case regex_constants::syntax_open_set:
1268          if(parse_inner_set(char_set))
1269             break;
1270          return true;
1271       case regex_constants::syntax_escape:
1272          {
1273             //
1274             // look ahead and see if this is a character class shortcut
1275             // \d \w \s etc...
1276             //
1277             ++m_position;
1278             if(this->m_traits.escape_syntax_type(*m_position)
1279                == regex_constants::escape_type_class)
1280             {
1281                char_class_type m = this->m_traits.lookup_classname(m_position, m_position+1);
1282                if(m != 0)
1283                {
1284                   char_set.add_class(m);
1285                   ++m_position;
1286                   break;
1287                }
1288             }
1289             else if(this->m_traits.escape_syntax_type(*m_position)
1290                == regex_constants::escape_type_not_class)
1291             {
1292                // negated character class:
1293                char_class_type m = this->m_traits.lookup_classname(m_position, m_position+1);
1294                if(m != 0)
1295                {
1296                   char_set.add_negated_class(m);
1297                   ++m_position;
1298                   break;
1299                }
1300             }
1301             // not a character class, just a regular escape:
1302             --m_position;
1303             parse_set_literal(char_set);
1304             break;
1305          }
1306       default:
1307          parse_set_literal(char_set);
1308          break;
1309       }
1310    }
1311    return m_position != m_end;
1312 }
1313
1314 template <class charT, class traits>
1315 bool basic_regex_parser<charT, traits>::parse_inner_set(basic_char_set<charT, traits>& char_set)
1316 {
1317    static const char* incomplete_message = "Character class declaration starting with [ terminated prematurely - either no ] was found or the set had no content.";
1318    //
1319    // we have either a character class [:name:]
1320    // a collating element [.name.]
1321    // or an equivalence class [=name=]
1322    //
1323    if(m_end == ++m_position)
1324    {
1325       fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1326       return false;
1327    }
1328    switch(this->m_traits.syntax_type(*m_position))
1329    {
1330    case regex_constants::syntax_dot:
1331       //
1332       // a collating element is treated as a literal:
1333       //
1334       --m_position;
1335       parse_set_literal(char_set);
1336       return true;
1337    case regex_constants::syntax_colon:
1338       {
1339       // check that character classes are actually enabled:
1340       if((this->flags() & (regbase::main_option_type | regbase::no_char_classes))
1341          == (regbase::basic_syntax_group  | regbase::no_char_classes))
1342       {
1343          --m_position;
1344          parse_set_literal(char_set);
1345          return true;
1346       }
1347       // skip the ':'
1348       if(m_end == ++m_position)
1349       {
1350          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1351          return false;
1352       }
1353       const charT* name_first = m_position;
1354       // skip at least one character, then find the matching ':]'
1355       if(m_end == ++m_position)
1356       {
1357          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1358          return false;
1359       }
1360       while((m_position != m_end)
1361          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_colon))
1362          ++m_position;
1363       const charT* name_last = m_position;
1364       if(m_end == m_position)
1365       {
1366          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1367          return false;
1368       }
1369       if((m_end == ++m_position)
1370          || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1371       {
1372          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1373          return false;
1374       }
1375       //
1376       // check for negated class:
1377       //
1378       bool negated = false;
1379       if(this->m_traits.syntax_type(*name_first) == regex_constants::syntax_caret)
1380       {
1381          ++name_first;
1382          negated = true;
1383       }
1384       typedef typename traits::char_class_type mask_type;
1385       mask_type m = this->m_traits.lookup_classname(name_first, name_last);
1386       if(m == 0)
1387       {
1388          if(char_set.empty() && (name_last - name_first == 1))
1389          {
1390             // maybe a special case:
1391             ++m_position;
1392             if( (m_position != m_end)
1393                && (this->m_traits.syntax_type(*m_position)
1394                   == regex_constants::syntax_close_set))
1395             {
1396                if(this->m_traits.escape_syntax_type(*name_first)
1397                   == regex_constants::escape_type_left_word)
1398                {
1399                   ++m_position;
1400                   this->append_state(syntax_element_word_start);
1401                   return false;
1402                }
1403                if(this->m_traits.escape_syntax_type(*name_first)
1404                   == regex_constants::escape_type_right_word)
1405                {
1406                   ++m_position;
1407                   this->append_state(syntax_element_word_end);
1408                   return false;
1409                }
1410             }
1411          }
1412          fail(regex_constants::error_ctype, name_first - m_base);
1413          return false;
1414       }
1415       if(negated == false)
1416          char_set.add_class(m);
1417       else
1418          char_set.add_negated_class(m);
1419       ++m_position;
1420       break;
1421    }
1422    case regex_constants::syntax_equal:
1423       {
1424       // skip the '='
1425       if(m_end == ++m_position)
1426       {
1427          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1428          return false;
1429       }
1430       const charT* name_first = m_position;
1431       // skip at least one character, then find the matching '=]'
1432       if(m_end == ++m_position)
1433       {
1434          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1435          return false;
1436       }
1437       while((m_position != m_end)
1438          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_equal))
1439          ++m_position;
1440       const charT* name_last = m_position;
1441       if(m_end == m_position)
1442       {
1443          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1444          return false;
1445       }
1446       if((m_end == ++m_position)
1447          || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1448       {
1449          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1450          return false;
1451       }
1452       string_type m = this->m_traits.lookup_collatename(name_first, name_last);
1453       if((0 == m.size()) || (m.size() > 2))
1454       {
1455          fail(regex_constants::error_collate, name_first - m_base);
1456          return false;
1457       }
1458       digraph<charT> d;
1459       d.first = m[0];
1460       if(m.size() > 1)
1461          d.second = m[1];
1462       else
1463          d.second = 0;
1464       char_set.add_equivalent(d);
1465       ++m_position;
1466       break;
1467    }
1468    default:
1469       --m_position;
1470       parse_set_literal(char_set);
1471       break;
1472    }
1473    return true;
1474 }
1475
1476 template <class charT, class traits>
1477 void basic_regex_parser<charT, traits>::parse_set_literal(basic_char_set<charT, traits>& char_set)
1478 {
1479    digraph<charT> start_range(get_next_set_literal(char_set));
1480    if(m_end == m_position)
1481    {
1482       fail(regex_constants::error_brack, m_position - m_base);
1483       return;
1484    }
1485    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_dash)
1486    {
1487       // we have a range:
1488       if(m_end == ++m_position)
1489       {
1490          fail(regex_constants::error_brack, m_position - m_base);
1491          return;
1492       }
1493       if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set)
1494       {
1495          digraph<charT> end_range = get_next_set_literal(char_set);
1496          char_set.add_range(start_range, end_range);
1497          if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_dash)
1498          {
1499             if(m_end == ++m_position)
1500             {
1501                fail(regex_constants::error_brack, m_position - m_base);
1502                return;
1503             }
1504             if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_set)
1505             {
1506                // trailing - :
1507                --m_position;
1508                return;
1509             }
1510             fail(regex_constants::error_range, m_position - m_base);
1511             return;
1512          }
1513          return;
1514       }
1515       --m_position;
1516    }
1517    char_set.add_single(start_range);
1518 }
1519
1520 template <class charT, class traits>
1521 digraph<charT> basic_regex_parser<charT, traits>::get_next_set_literal(basic_char_set<charT, traits>& char_set)
1522 {
1523    digraph<charT> result;
1524    switch(this->m_traits.syntax_type(*m_position))
1525    {
1526    case regex_constants::syntax_dash:
1527       if(!char_set.empty())
1528       {
1529          // see if we are at the end of the set:
1530          if((++m_position == m_end) || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1531          {
1532             fail(regex_constants::error_range, m_position - m_base);
1533             return result;
1534          }
1535          --m_position;
1536       }
1537       result.first = *m_position++;
1538       return result;
1539    case regex_constants::syntax_escape:
1540       // check to see if escapes are supported first:
1541       if(this->flags() & regex_constants::no_escape_in_lists)
1542       {
1543          result = *m_position++;
1544          break;
1545       }
1546       ++m_position;
1547       result = unescape_character();
1548       break;
1549    case regex_constants::syntax_open_set:
1550    {
1551       if(m_end == ++m_position)
1552       {
1553          fail(regex_constants::error_collate, m_position - m_base);
1554          return result;
1555       }
1556       if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_dot)
1557       {
1558          --m_position;
1559          result.first = *m_position;
1560          ++m_position;
1561          return result;
1562       }
1563       if(m_end == ++m_position)
1564       {
1565          fail(regex_constants::error_collate, m_position - m_base);
1566          return result;
1567       }
1568       const charT* name_first = m_position;
1569       // skip at least one character, then find the matching ':]'
1570       if(m_end == ++m_position)
1571       {
1572          fail(regex_constants::error_collate, name_first - m_base);
1573          return result;
1574       }
1575       while((m_position != m_end)
1576          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_dot))
1577          ++m_position;
1578       const charT* name_last = m_position;
1579       if(m_end == m_position)
1580       {
1581          fail(regex_constants::error_collate, name_first - m_base);
1582          return result;
1583       }
1584       if((m_end == ++m_position)
1585          || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1586       {
1587          fail(regex_constants::error_collate, name_first - m_base);
1588          return result;
1589       }
1590       ++m_position;
1591       string_type s = this->m_traits.lookup_collatename(name_first, name_last);
1592       if(s.empty() || (s.size() > 2))
1593       {
1594          fail(regex_constants::error_collate, name_first - m_base);
1595          return result;
1596       }
1597       result.first = s[0];
1598       if(s.size() > 1)
1599          result.second = s[1];
1600       else
1601          result.second = 0;
1602       return result;
1603    }
1604    default:
1605       result = *m_position++;
1606    }
1607    return result;
1608 }
1609
1610 //
1611 // does a value fit in the specified charT type?
1612 //
1613 template <class charT>
1614 bool valid_value(charT, int v, const mpl::true_&)
1615 {
1616    return (v >> (sizeof(charT) * CHAR_BIT)) == 0;
1617 }
1618 template <class charT>
1619 bool valid_value(charT, int, const mpl::false_&)
1620 {
1621    return true; // v will alsways fit in a charT
1622 }
1623 template <class charT>
1624 bool valid_value(charT c, int v)
1625 {
1626    return valid_value(c, v, mpl::bool_<(sizeof(charT) < sizeof(int))>());
1627 }
1628
1629 template <class charT, class traits>
1630 charT basic_regex_parser<charT, traits>::unescape_character()
1631 {
1632 #ifdef BOOST_MSVC
1633 #pragma warning(push)
1634 #pragma warning(disable:4127)
1635 #endif
1636    charT result(0);
1637    if(m_position == m_end)
1638    {
1639       fail(regex_constants::error_escape, m_position - m_base, "Escape sequence terminated prematurely.");
1640       return false;
1641    }
1642    switch(this->m_traits.escape_syntax_type(*m_position))
1643    {
1644    case regex_constants::escape_type_control_a:
1645       result = charT('\a');
1646       break;
1647    case regex_constants::escape_type_e:
1648       result = charT(27);
1649       break;
1650    case regex_constants::escape_type_control_f:
1651       result = charT('\f');
1652       break;
1653    case regex_constants::escape_type_control_n:
1654       result = charT('\n');
1655       break;
1656    case regex_constants::escape_type_control_r:
1657       result = charT('\r');
1658       break;
1659    case regex_constants::escape_type_control_t:
1660       result = charT('\t');
1661       break;
1662    case regex_constants::escape_type_control_v:
1663       result = charT('\v');
1664       break;
1665    case regex_constants::escape_type_word_assert:
1666       result = charT('\b');
1667       break;
1668    case regex_constants::escape_type_ascii_control:
1669       ++m_position;
1670       if(m_position == m_end)
1671       {
1672          // Rewind to start of escape:
1673          --m_position;
1674          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1675          fail(regex_constants::error_escape, m_position - m_base, "ASCII escape sequence terminated prematurely.");
1676          return result;
1677       }
1678       result = static_cast<charT>(*m_position % 32);
1679       break;
1680    case regex_constants::escape_type_hex:
1681       ++m_position;
1682       if(m_position == m_end)
1683       {
1684          // Rewind to start of escape:
1685          --m_position;
1686          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1687          fail(regex_constants::error_escape, m_position - m_base, "Hexadecimal escape sequence terminated prematurely.");
1688          return result;
1689       }
1690       // maybe have \x{ddd}
1691       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_open_brace)
1692       {
1693          ++m_position;
1694          if(m_position == m_end)
1695          {
1696             // Rewind to start of escape:
1697             --m_position;
1698             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1699             fail(regex_constants::error_escape, m_position - m_base, "Missing } in hexadecimal escape sequence.");
1700             return result;
1701          }
1702          int i = this->m_traits.toi(m_position, m_end, 16);
1703          if((m_position == m_end)
1704             || (i < 0)
1705             || ((std::numeric_limits<charT>::is_specialized) && (i > (int)(std::numeric_limits<charT>::max)()))
1706             || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_brace))
1707          {
1708             // Rewind to start of escape:
1709             --m_position;
1710             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1711             fail(regex_constants::error_badbrace, m_position - m_base, "Hexadecimal escape sequence was invalid.");
1712             return result;
1713          }
1714          ++m_position;
1715          result = charT(i);
1716       }
1717       else
1718       {
1719          std::ptrdiff_t len = (std::min)(static_cast<std::ptrdiff_t>(2), static_cast<std::ptrdiff_t>(m_end - m_position));
1720          int i = this->m_traits.toi(m_position, m_position + len, 16);
1721          if((i < 0)
1722             || !valid_value(charT(0), i))
1723          {
1724             // Rewind to start of escape:
1725             --m_position;
1726             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1727             fail(regex_constants::error_escape, m_position - m_base, "Escape sequence did not encode a valid character.");
1728             return result;
1729          }
1730          result = charT(i);
1731       }
1732       return result;
1733    case regex_constants::syntax_digit:
1734       {
1735       // an octal escape sequence, the first character must be a zero
1736       // followed by up to 3 octal digits:
1737       std::ptrdiff_t len = (std::min)(::boost::re_detail::distance(m_position, m_end), static_cast<std::ptrdiff_t>(4));
1738       const charT* bp = m_position;
1739       int val = this->m_traits.toi(bp, bp + 1, 8);
1740       if(val != 0)
1741       {
1742          // Rewind to start of escape:
1743          --m_position;
1744          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1745          // Oops not an octal escape after all:
1746          fail(regex_constants::error_escape, m_position - m_base, "Invalid octal escape sequence.");
1747          return result;
1748       }
1749       val = this->m_traits.toi(m_position, m_position + len, 8);
1750       if(val < 0)
1751       {
1752          // Rewind to start of escape:
1753          --m_position;
1754          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1755          fail(regex_constants::error_escape, m_position - m_base, "Octal escape sequence is invalid.");
1756          return result;
1757       }
1758       return static_cast<charT>(val);
1759       }
1760    case regex_constants::escape_type_named_char:
1761       {
1762          ++m_position;
1763          if(m_position == m_end)
1764          {
1765             // Rewind to start of escape:
1766             --m_position;
1767             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1768             fail(regex_constants::error_escape, m_position - m_base);
1769             return false;
1770          }
1771          // maybe have \N{name}
1772          if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_open_brace)
1773          {
1774             const charT* base = m_position;
1775             // skip forward until we find enclosing brace:
1776             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_brace))
1777                ++m_position;
1778             if(m_position == m_end)
1779             {
1780                // Rewind to start of escape:
1781                --m_position;
1782                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1783                fail(regex_constants::error_escape, m_position - m_base);
1784                return false;
1785             }
1786             string_type s = this->m_traits.lookup_collatename(++base, m_position++);
1787             if(s.empty())
1788             {
1789                // Rewind to start of escape:
1790                --m_position;
1791                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1792                fail(regex_constants::error_collate, m_position - m_base);
1793                return false;
1794             }
1795             if(s.size() == 1)
1796             {
1797                return s[0];
1798             }
1799          }
1800          // fall through is a failure:
1801          // Rewind to start of escape:
1802          --m_position;
1803          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1804          fail(regex_constants::error_escape, m_position - m_base);
1805          return false;
1806       }
1807    default:
1808       result = *m_position;
1809       break;
1810    }
1811    ++m_position;
1812    return result;
1813 #ifdef BOOST_MSVC
1814 #pragma warning(pop)
1815 #endif
1816 }
1817
1818 template <class charT, class traits>
1819 bool basic_regex_parser<charT, traits>::parse_backref()
1820 {
1821    BOOST_ASSERT(m_position != m_end);
1822    const charT* pc = m_position;
1823    int i = this->m_traits.toi(pc, pc + 1, 10);
1824    if((i == 0) || (((this->flags() & regbase::main_option_type) == regbase::perl_syntax_group) && (this->flags() & regbase::no_bk_refs)))
1825    {
1826       // not a backref at all but an octal escape sequence:
1827       charT c = unescape_character();
1828       this->append_literal(c);
1829    }
1830    else if((i > 0) && (this->m_backrefs & (1u << (i-1))))
1831    {
1832       m_position = pc;
1833       re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_backref, sizeof(re_brace)));
1834       pb->index = i;
1835       pb->icase = this->flags() & regbase::icase;
1836    }
1837    else
1838    {
1839       // Rewind to start of escape:
1840       --m_position;
1841       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1842       fail(regex_constants::error_backref, m_position - m_base);
1843       return false;
1844    }
1845    return true;
1846 }
1847
1848 template <class charT, class traits>
1849 bool basic_regex_parser<charT, traits>::parse_QE()
1850 {
1851 #ifdef BOOST_MSVC
1852 #pragma warning(push)
1853 #pragma warning(disable:4127)
1854 #endif
1855    //
1856    // parse a \Q...\E sequence:
1857    //
1858    ++m_position; // skip the Q
1859    const charT* start = m_position;
1860    const charT* end;
1861    do
1862    {
1863       while((m_position != m_end)
1864          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape))
1865          ++m_position;
1866       if(m_position == m_end)
1867       {
1868          //  a \Q...\E sequence may terminate with the end of the expression:
1869          end = m_position;
1870          break;
1871       }
1872       if(++m_position == m_end) // skip the escape
1873       {
1874          fail(regex_constants::error_escape, m_position - m_base, "Unterminated \\Q...\\E sequence.");
1875          return false;
1876       }
1877       // check to see if it's a \E:
1878       if(this->m_traits.escape_syntax_type(*m_position) == regex_constants::escape_type_E)
1879       {
1880          ++m_position;
1881          end = m_position - 2;
1882          break;
1883       }
1884       // otherwise go round again:
1885    }while(true);
1886    //
1887    // now add all the character between the two escapes as literals:
1888    //
1889    while(start != end)
1890    {
1891       this->append_literal(*start);
1892       ++start;
1893    }
1894    return true;
1895 #ifdef BOOST_MSVC
1896 #pragma warning(pop)
1897 #endif
1898 }
1899
1900 template <class charT, class traits>
1901 bool basic_regex_parser<charT, traits>::parse_perl_extension()
1902 {
1903    if(++m_position == m_end)
1904    {
1905       // Rewind to start of (? sequence:
1906       --m_position;
1907       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
1908       fail(regex_constants::error_perl_extension, m_position - m_base);
1909       return false;
1910    }
1911    //
1912    // treat comments as a special case, as these
1913    // are the only ones that don't start with a leading
1914    // startmark state:
1915    //
1916    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_hash)
1917    {
1918       while((m_position != m_end)
1919          && (this->m_traits.syntax_type(*m_position++) != regex_constants::syntax_close_mark))
1920       {}
1921       return true;
1922    }
1923    //
1924    // backup some state, and prepare the way:
1925    //
1926    int markid = 0;
1927    std::ptrdiff_t jump_offset = 0;
1928    re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_startmark, sizeof(re_brace)));
1929    pb->icase = this->flags() & regbase::icase;
1930    std::ptrdiff_t last_paren_start = this->getoffset(pb);
1931    // back up insertion point for alternations, and set new point:
1932    std::ptrdiff_t last_alt_point = m_alt_insert_point;
1933    this->m_pdata->m_data.align();
1934    m_alt_insert_point = this->m_pdata->m_data.size();
1935    std::ptrdiff_t expected_alt_point = m_alt_insert_point;
1936    bool restore_flags = true;
1937    regex_constants::syntax_option_type old_flags = this->flags();
1938    bool old_case_change = m_has_case_change;
1939    m_has_case_change = false;
1940    charT name_delim;
1941    int mark_reset = m_mark_reset;
1942    int max_mark = m_max_mark;
1943    m_mark_reset = -1;
1944    m_max_mark = m_mark_count;
1945    int v;
1946    //
1947    // select the actual extension used:
1948    //
1949    switch(this->m_traits.syntax_type(*m_position))
1950    {
1951    case regex_constants::syntax_or:
1952       m_mark_reset = m_mark_count;
1953       // fall through:
1954    case regex_constants::syntax_colon:
1955       //
1956       // a non-capturing mark:
1957       //
1958       pb->index = markid = 0;
1959       ++m_position;
1960       break;
1961    case regex_constants::syntax_digit:
1962       {
1963       //
1964       // a recursive subexpression:
1965       //
1966       v = this->m_traits.toi(m_position, m_end, 10);
1967       if((v < 0) || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
1968       {
1969          // Rewind to start of (? sequence:
1970          --m_position;
1971          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
1972          fail(regex_constants::error_perl_extension, m_position - m_base, "The recursive sub-expression refers to an invalid marking group, or is unterminated.");
1973          return false;
1974       }
1975 insert_recursion:
1976       pb->index = markid = 0;
1977       re_recurse* pr = static_cast<re_recurse*>(this->append_state(syntax_element_recurse, sizeof(re_recurse)));
1978       pr->alt.i = v;
1979       pr->state_id = 0;
1980       static_cast<re_case*>(
1981             this->append_state(syntax_element_toggle_case, sizeof(re_case))
1982             )->icase = this->flags() & regbase::icase;
1983       break;
1984       }
1985    case regex_constants::syntax_plus:
1986       //
1987       // A forward-relative recursive subexpression:
1988       //
1989       ++m_position;
1990       v = this->m_traits.toi(m_position, m_end, 10);
1991       if((v <= 0) || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
1992       {
1993          // Rewind to start of (? sequence:
1994          --m_position;
1995          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
1996          fail(regex_constants::error_perl_extension, m_position - m_base, "An invalid or unterminated recursive sub-expression.");
1997          return false;
1998       }
1999       v += m_mark_count;
2000       goto insert_recursion;
2001    case regex_constants::syntax_dash:
2002       //
2003       // Possibly a backward-relative recursive subexpression:
2004       //
2005       ++m_position;
2006       v = this->m_traits.toi(m_position, m_end, 10);
2007       if(v <= 0)
2008       {
2009          --m_position;
2010          // Oops not a relative recursion at all, but a (?-imsx) group:
2011          goto option_group_jump;
2012       }
2013       v = m_mark_count + 1 - v;
2014       if(v <= 0)
2015       {
2016          // Rewind to start of (? sequence:
2017          --m_position;
2018          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2019          fail(regex_constants::error_perl_extension, m_position - m_base, "An invalid or unterminated recursive sub-expression.");
2020          return false;
2021       }
2022       goto insert_recursion;
2023    case regex_constants::syntax_equal:
2024       pb->index = markid = -1;
2025       ++m_position;
2026       jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2027       this->m_pdata->m_data.align();
2028       m_alt_insert_point = this->m_pdata->m_data.size();
2029       break;
2030    case regex_constants::syntax_not:
2031       pb->index = markid = -2;
2032       ++m_position;
2033       jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2034       this->m_pdata->m_data.align();
2035       m_alt_insert_point = this->m_pdata->m_data.size();
2036       break;
2037    case regex_constants::escape_type_left_word:
2038       {
2039          // a lookbehind assertion:
2040          if(++m_position == m_end)
2041          {
2042             // Rewind to start of (? sequence:
2043             --m_position;
2044             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2045             fail(regex_constants::error_perl_extension, m_position - m_base);
2046             return false;
2047          }
2048          regex_constants::syntax_type t = this->m_traits.syntax_type(*m_position);
2049          if(t == regex_constants::syntax_not)
2050             pb->index = markid = -2;
2051          else if(t == regex_constants::syntax_equal)
2052             pb->index = markid = -1;
2053          else
2054          {
2055             // Probably a named capture which also starts (?< :
2056             name_delim = '>';
2057             --m_position;
2058             goto named_capture_jump;
2059          }
2060          ++m_position;
2061          jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2062          this->append_state(syntax_element_backstep, sizeof(re_brace));
2063          this->m_pdata->m_data.align();
2064          m_alt_insert_point = this->m_pdata->m_data.size();
2065          break;
2066       }
2067    case regex_constants::escape_type_right_word:
2068       //
2069       // an independent sub-expression:
2070       //
2071       pb->index = markid = -3;
2072       ++m_position;
2073       jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2074       this->m_pdata->m_data.align();
2075       m_alt_insert_point = this->m_pdata->m_data.size();
2076       break;
2077    case regex_constants::syntax_open_mark:
2078       {
2079       // a conditional expression:
2080       pb->index = markid = -4;
2081       if(++m_position == m_end)
2082       {
2083          // Rewind to start of (? sequence:
2084          --m_position;
2085          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2086          fail(regex_constants::error_perl_extension, m_position - m_base);
2087          return false;
2088       }
2089       v = this->m_traits.toi(m_position, m_end, 10);
2090       if(*m_position == charT('R'))
2091       {
2092          if(++m_position == m_end)
2093          {
2094             // Rewind to start of (? sequence:
2095             --m_position;
2096             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2097             fail(regex_constants::error_perl_extension, m_position - m_base);
2098             return false;
2099          }
2100          if(*m_position == charT('&'))
2101          {
2102             const charT* base = ++m_position;
2103             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
2104                ++m_position;
2105             if(m_position == m_end)
2106             {
2107                // Rewind to start of (? sequence:
2108                --m_position;
2109                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2110                fail(regex_constants::error_perl_extension, m_position - m_base);
2111                return false;
2112             }
2113             v = -static_cast<int>(hash_value_from_capture_name(base, m_position));
2114          }
2115          else
2116          {
2117             v = -this->m_traits.toi(m_position, m_end, 10);
2118          }
2119          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2120          br->index = v < 0 ? (v - 1) : 0;
2121          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2122          {
2123             // Rewind to start of (? sequence:
2124             --m_position;
2125             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2126             fail(regex_constants::error_perl_extension, m_position - m_base);
2127             return false;
2128          }
2129          if(++m_position == m_end)
2130          {
2131             // Rewind to start of (? sequence:
2132             --m_position;
2133             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2134             fail(regex_constants::error_perl_extension, m_position - m_base);
2135             return false;
2136          }
2137       }
2138       else if((*m_position == charT('\'')) || (*m_position == charT('<')))
2139       {
2140          const charT* base = ++m_position;
2141          while((m_position != m_end) && (*m_position != charT('>')) && (*m_position != charT('\'')))
2142             ++m_position;
2143          if(m_position == m_end)
2144          {
2145             // Rewind to start of (? sequence:
2146             --m_position;
2147             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2148             fail(regex_constants::error_perl_extension, m_position - m_base);
2149             return false;
2150          }
2151          v = static_cast<int>(hash_value_from_capture_name(base, m_position));
2152          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2153          br->index = v;
2154          if(((*m_position != charT('>')) && (*m_position != charT('\''))) || (++m_position == m_end))
2155          {
2156             // Rewind to start of (? sequence:
2157             --m_position;
2158             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2159             fail(regex_constants::error_perl_extension, m_position - m_base, "Unterminated named capture.");
2160             return false;
2161          }
2162          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2163          {
2164             // Rewind to start of (? sequence:
2165             --m_position;
2166             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2167             fail(regex_constants::error_perl_extension, m_position - m_base);
2168             return false;
2169          }
2170          if(++m_position == m_end)
2171          {
2172             // Rewind to start of (? sequence:
2173             --m_position;
2174             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2175             fail(regex_constants::error_perl_extension, m_position - m_base);
2176             return false;
2177          }
2178       }
2179       else if(*m_position == charT('D'))
2180       {
2181          const char* def = "DEFINE";
2182          while(*def && (m_position != m_end) && (*m_position == charT(*def)))
2183             ++m_position, ++def;
2184          if((m_position == m_end) || *def)
2185          {
2186             // Rewind to start of (? sequence:
2187             --m_position;
2188             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2189             fail(regex_constants::error_perl_extension, m_position - m_base);
2190             return false;
2191          }
2192          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2193          br->index = 9999; // special magic value!
2194          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2195          {
2196             // Rewind to start of (? sequence:
2197             --m_position;
2198             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2199             fail(regex_constants::error_perl_extension, m_position - m_base);
2200             return false;
2201          }
2202          if(++m_position == m_end)
2203          {
2204             // Rewind to start of (? sequence:
2205             --m_position;
2206             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2207             fail(regex_constants::error_perl_extension, m_position - m_base);
2208             return false;
2209          }
2210       }
2211       else if(v > 0)
2212       {
2213          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2214          br->index = v;
2215          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2216          {
2217             // Rewind to start of (? sequence:
2218             --m_position;
2219             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2220             fail(regex_constants::error_perl_extension, m_position - m_base);
2221             return false;
2222          }
2223          if(++m_position == m_end)
2224          {
2225             // Rewind to start of (? sequence:
2226             --m_position;
2227             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2228             fail(regex_constants::error_perl_extension, m_position - m_base);
2229             return false;
2230          }
2231       }
2232       else
2233       {
2234          // verify that we have a lookahead or lookbehind assert:
2235          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_question)
2236          {
2237             // Rewind to start of (? sequence:
2238             --m_position;
2239             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2240             fail(regex_constants::error_perl_extension, m_position - m_base);
2241             return false;
2242          }
2243          if(++m_position == m_end)
2244          {
2245             // Rewind to start of (? sequence:
2246             --m_position;
2247             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2248             fail(regex_constants::error_perl_extension, m_position - m_base);
2249             return false;
2250          }
2251          if(this->m_traits.syntax_type(*m_position) == regex_constants::escape_type_left_word)
2252          {
2253             if(++m_position == m_end)
2254             {
2255                // Rewind to start of (? sequence:
2256                --m_position;
2257                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2258                fail(regex_constants::error_perl_extension, m_position - m_base);
2259                return false;
2260             }
2261             if((this->m_traits.syntax_type(*m_position) != regex_constants::syntax_equal)
2262                && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_not))
2263             {
2264                // Rewind to start of (? sequence:
2265                --m_position;
2266                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2267                fail(regex_constants::error_perl_extension, m_position - m_base);
2268                return false;
2269             }
2270             m_position -= 3;
2271          }
2272          else
2273          {
2274             if((this->m_traits.syntax_type(*m_position) != regex_constants::syntax_equal)
2275                && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_not))
2276             {
2277                // Rewind to start of (? sequence:
2278                --m_position;
2279                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2280                fail(regex_constants::error_perl_extension, m_position - m_base);
2281                return false;
2282             }
2283             m_position -= 2;
2284          }
2285       }
2286       break;
2287       }
2288    case regex_constants::syntax_close_mark:
2289       // Rewind to start of (? sequence:
2290       --m_position;
2291       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2292       fail(regex_constants::error_perl_extension, m_position - m_base);
2293       return false;
2294    case regex_constants::escape_type_end_buffer:
2295       {
2296       name_delim = *m_position;
2297 named_capture_jump:
2298       markid = 0;
2299       if(0 == (this->flags() & regbase::nosubs))
2300       {
2301          markid = ++m_mark_count;
2302    #ifndef BOOST_NO_STD_DISTANCE
2303          if(this->flags() & regbase::save_subexpression_location)
2304             this->m_pdata->m_subs.push_back(std::pair<std::size_t, std::size_t>(std::distance(m_base, m_position) - 2, 0));
2305    #else
2306          if(this->flags() & regbase::save_subexpression_location)
2307             this->m_pdata->m_subs.push_back(std::pair<std::size_t, std::size_t>((m_position - m_base) - 2, 0));
2308    #endif
2309       }
2310       pb->index = markid;
2311       const charT* base = ++m_position;
2312       if(m_position == m_end)
2313       {
2314          // Rewind to start of (? sequence:
2315          --m_position;
2316          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2317          fail(regex_constants::error_perl_extension, m_position - m_base);
2318          return false;
2319       }
2320       while((m_position != m_end) && (*m_position != name_delim))
2321          ++m_position;
2322       if(m_position == m_end)
2323       {
2324          // Rewind to start of (? sequence:
2325          --m_position;
2326          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2327          fail(regex_constants::error_perl_extension, m_position - m_base);
2328          return false;
2329       }
2330       this->m_pdata->set_name(base, m_position, markid);
2331       ++m_position;
2332       break;
2333       }
2334    default:
2335       if(*m_position == charT('R'))
2336       {
2337          ++m_position;
2338          v = 0;
2339          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2340          {
2341             // Rewind to start of (? sequence:
2342             --m_position;
2343             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2344             fail(regex_constants::error_perl_extension, m_position - m_base);
2345             return false;
2346          }
2347          goto insert_recursion;
2348       }
2349       if(*m_position == charT('&'))
2350       {
2351          ++m_position;
2352          const charT* base = m_position;
2353          while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
2354             ++m_position;
2355          if(m_position == m_end)
2356          {
2357             // Rewind to start of (? sequence:
2358             --m_position;
2359             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2360             fail(regex_constants::error_perl_extension, m_position - m_base);
2361             return false;
2362          }
2363          v = static_cast<int>(hash_value_from_capture_name(base, m_position));
2364          goto insert_recursion;
2365       }
2366       if(*m_position == charT('P'))
2367       {
2368          ++m_position;
2369          if(m_position == m_end)
2370          {
2371             // Rewind to start of (? sequence:
2372             --m_position;
2373             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2374             fail(regex_constants::error_perl_extension, m_position - m_base);
2375             return false;
2376          }
2377          if(*m_position == charT('>'))
2378          {
2379             ++m_position;
2380             const charT* base = m_position;
2381             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
2382                ++m_position;
2383             if(m_position == m_end)
2384             {
2385                // Rewind to start of (? sequence:
2386                --m_position;
2387                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2388                fail(regex_constants::error_perl_extension, m_position - m_base);
2389                return false;
2390             }
2391             v = static_cast<int>(hash_value_from_capture_name(base, m_position));
2392             goto insert_recursion;
2393          }
2394       }
2395       //
2396       // lets assume that we have a (?imsx) group and try and parse it:
2397       //
2398 option_group_jump:
2399       regex_constants::syntax_option_type opts = parse_options();
2400       if(m_position == m_end)
2401       {
2402          // Rewind to start of (? sequence:
2403          --m_position;
2404          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2405          fail(regex_constants::error_perl_extension, m_position - m_base);
2406          return false;
2407       }
2408       // make a note of whether we have a case change:
2409       m_has_case_change = ((opts & regbase::icase) != (this->flags() & regbase::icase));
2410       pb->index = markid = 0;
2411       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_mark)
2412       {
2413          // update flags and carry on as normal:
2414          this->flags(opts);
2415          restore_flags = false;
2416          old_case_change |= m_has_case_change; // defer end of scope by one ')'
2417       }
2418       else if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_colon)
2419       {
2420          // update flags and carry on until the matching ')' is found:
2421          this->flags(opts);
2422          ++m_position;
2423       }
2424       else
2425       {
2426          // Rewind to start of (? sequence:
2427          --m_position;
2428          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2429          fail(regex_constants::error_perl_extension, m_position - m_base);
2430          return false;
2431       }
2432
2433       // finally append a case change state if we need it:
2434       if(m_has_case_change)
2435       {
2436          static_cast<re_case*>(
2437             this->append_state(syntax_element_toggle_case, sizeof(re_case))
2438             )->icase = opts & regbase::icase;
2439       }
2440
2441    }
2442    //
2443    // now recursively add more states, this will terminate when we get to a
2444    // matching ')' :
2445    //
2446    parse_all();
2447    //
2448    // Unwind alternatives:
2449    //
2450    if(0 == unwind_alts(last_paren_start))
2451    {
2452       // Rewind to start of (? sequence:
2453       --m_position;
2454       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2455       fail(regex_constants::error_perl_extension, m_position - m_base, "Invalid alternation operators within (?...) block.");
2456       return false;
2457    }
2458    //
2459    // we either have a ')' or we have run out of characters prematurely:
2460    //
2461    if(m_position == m_end)
2462    {
2463       // Rewind to start of (? sequence:
2464       --m_position;
2465       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2466       this->fail(regex_constants::error_paren, ::boost::re_detail::distance(m_base, m_end));
2467       return false;
2468    }
2469    BOOST_ASSERT(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_mark);
2470    ++m_position;
2471    //
2472    // restore the flags:
2473    //
2474    if(restore_flags)
2475    {
2476       // append a case change state if we need it:
2477       if(m_has_case_change)
2478       {
2479          static_cast<re_case*>(
2480             this->append_state(syntax_element_toggle_case, sizeof(re_case))
2481             )->icase = old_flags & regbase::icase;
2482       }
2483       this->flags(old_flags);
2484    }
2485    //
2486    // set up the jump pointer if we have one:
2487    //
2488    if(jump_offset)
2489    {
2490       this->m_pdata->m_data.align();
2491       re_jump* jmp = static_cast<re_jump*>(this->getaddress(jump_offset));
2492       jmp->alt.i = this->m_pdata->m_data.size() - this->getoffset(jmp);
2493       if(this->m_last_state == jmp)
2494       {
2495          // Oops... we didn't have anything inside the assertion:
2496          // Rewind to start of (? sequence:
2497          --m_position;
2498          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2499          fail(regex_constants::error_perl_extension, m_position - m_base, "Invalid or empty zero width assertion.");
2500          return false;
2501       }
2502    }
2503    //
2504    // verify that if this is conditional expression, that we do have
2505    // an alternative, if not add one:
2506    //
2507    if(markid == -4)
2508    {
2509       re_syntax_base* b = this->getaddress(expected_alt_point);
2510       // Make sure we have exactly one alternative following this state:
2511       if(b->type != syntax_element_alt)
2512       {
2513          re_alt* alt = static_cast<re_alt*>(this->insert_state(expected_alt_point, syntax_element_alt, sizeof(re_alt)));
2514          alt->alt.i = this->m_pdata->m_data.size() - this->getoffset(alt);
2515       }
2516       else if(this->getaddress(static_cast<re_alt*>(b)->alt.i, b)->type == syntax_element_alt)
2517       {
2518          // Can't have seen more than one alternative:
2519          // Rewind to start of (? sequence:
2520          --m_position;
2521          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2522          fail(regex_constants::error_bad_pattern, m_position - m_base, "More than one alternation operator | was encountered inside a conditional expression.");
2523          return false;
2524       }
2525       else
2526       {
2527          // We must *not* have seen an alternative inside a (DEFINE) block:
2528          b = this->getaddress(b->next.i, b);
2529          if((b->type == syntax_element_assert_backref) && (static_cast<re_brace*>(b)->index == 9999))
2530          {
2531             // Rewind to start of (? sequence:
2532             --m_position;
2533             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2534             fail(regex_constants::error_bad_pattern, m_position - m_base, "Alternation operators are not allowed inside a DEFINE block.");
2535             return false;
2536          }
2537       }
2538       // check for invalid repetition of next state:
2539       b = this->getaddress(expected_alt_point);
2540       b = this->getaddress(static_cast<re_alt*>(b)->next.i, b);
2541       if((b->type != syntax_element_assert_backref)
2542          && (b->type != syntax_element_startmark))
2543       {
2544          // Rewind to start of (? sequence:
2545          --m_position;
2546          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2547          fail(regex_constants::error_badrepeat, m_position - m_base, "A repetition operator cannot be applied to a zero-width assertion.");
2548          return false;
2549       }
2550    }
2551    //
2552    // append closing parenthesis state:
2553    //
2554    pb = static_cast<re_brace*>(this->append_state(syntax_element_endmark, sizeof(re_brace)));
2555    pb->index = markid;
2556    pb->icase = this->flags() & regbase::icase;
2557    this->m_paren_start = last_paren_start;
2558    //
2559    // restore the alternate insertion point:
2560    //
2561    this->m_alt_insert_point = last_alt_point;
2562    //
2563    // and the case change data:
2564    //
2565    m_has_case_change = old_case_change;
2566    //
2567    // And the mark_reset data:
2568    //
2569    if(m_max_mark > m_mark_count)
2570    {
2571       m_mark_count = m_max_mark;
2572    }
2573    m_mark_reset = mark_reset;
2574    m_max_mark = max_mark;
2575
2576
2577    if(markid > 0)
2578    {
2579 #ifndef BOOST_NO_STD_DISTANCE
2580       if(this->flags() & regbase::save_subexpression_location)
2581          this->m_pdata->m_subs.at(markid - 1).second = std::distance(m_base, m_position) - 1;
2582 #else
2583       if(this->flags() & regbase::save_subexpression_location)
2584          this->m_pdata->m_subs.at(markid - 1).second = (m_position - m_base) - 1;
2585 #endif
2586       //
2587       // allow backrefs to this mark:
2588       //
2589       if((markid > 0) && (markid < (int)(sizeof(unsigned) * CHAR_BIT)))
2590          this->m_backrefs |= 1u << (markid - 1);
2591    }
2592    return true;
2593 }
2594
2595 template <class charT, class traits>
2596 bool basic_regex_parser<charT, traits>::add_emacs_code(bool negate)
2597 {
2598    //
2599    // parses an emacs style \sx or \Sx construct.
2600    //
2601    if(++m_position == m_end)
2602    {
2603       // Rewind to start of sequence:
2604       --m_position;
2605       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
2606       fail(regex_constants::error_escape, m_position - m_base);
2607       return false;
2608    }
2609    basic_char_set<charT, traits> char_set;
2610    if(negate)
2611       char_set.negate();
2612
2613    static const charT s_punct[5] = { 'p', 'u', 'n', 'c', 't', };
2614
2615    switch(*m_position)
2616    {
2617    case 's':
2618    case ' ':
2619       char_set.add_class(this->m_mask_space);
2620       break;
2621    case 'w':
2622       char_set.add_class(this->m_word_mask);
2623       break;
2624    case '_':
2625       char_set.add_single(digraph<charT>(charT('$')));
2626       char_set.add_single(digraph<charT>(charT('&')));
2627       char_set.add_single(digraph<charT>(charT('*')));
2628       char_set.add_single(digraph<charT>(charT('+')));
2629       char_set.add_single(digraph<charT>(charT('-')));
2630       char_set.add_single(digraph<charT>(charT('_')));
2631       char_set.add_single(digraph<charT>(charT('<')));
2632       char_set.add_single(digraph<charT>(charT('>')));
2633       break;
2634    case '.':
2635       char_set.add_class(this->m_traits.lookup_classname(s_punct, s_punct+5));
2636       break;
2637    case '(':
2638       char_set.add_single(digraph<charT>(charT('(')));
2639       char_set.add_single(digraph<charT>(charT('[')));
2640       char_set.add_single(digraph<charT>(charT('{')));
2641       break;
2642    case ')':
2643       char_set.add_single(digraph<charT>(charT(')')));
2644       char_set.add_single(digraph<charT>(charT(']')));
2645       char_set.add_single(digraph<charT>(charT('}')));
2646       break;
2647    case '"':
2648       char_set.add_single(digraph<charT>(charT('"')));
2649       char_set.add_single(digraph<charT>(charT('\'')));
2650       char_set.add_single(digraph<charT>(charT('`')));
2651       break;
2652    case '\'':
2653       char_set.add_single(digraph<charT>(charT('\'')));
2654       char_set.add_single(digraph<charT>(charT(',')));
2655       char_set.add_single(digraph<charT>(charT('#')));
2656       break;
2657    case '<':
2658       char_set.add_single(digraph<charT>(charT(';')));
2659       break;
2660    case '>':
2661       char_set.add_single(digraph<charT>(charT('\n')));
2662       char_set.add_single(digraph<charT>(charT('\f')));
2663       break;
2664    default:
2665       fail(regex_constants::error_ctype, m_position - m_base);
2666       return false;
2667    }
2668    if(0 == this->append_set(char_set))
2669    {
2670       fail(regex_constants::error_ctype, m_position - m_base);
2671       return false;
2672    }
2673    ++m_position;
2674    return true;
2675 }
2676
2677 template <class charT, class traits>
2678 regex_constants::syntax_option_type basic_regex_parser<charT, traits>::parse_options()
2679 {
2680    // we have a (?imsx-imsx) group, convert it into a set of flags:
2681    regex_constants::syntax_option_type f = this->flags();
2682    bool breakout = false;
2683    do
2684    {
2685       switch(*m_position)
2686       {
2687       case 's':
2688          f |= regex_constants::mod_s;
2689          f &= ~regex_constants::no_mod_s;
2690          break;
2691       case 'm':
2692          f &= ~regex_constants::no_mod_m;
2693          break;
2694       case 'i':
2695          f |= regex_constants::icase;
2696          break;
2697       case 'x':
2698          f |= regex_constants::mod_x;
2699          break;
2700       default:
2701          breakout = true;
2702          continue;
2703       }
2704       if(++m_position == m_end)
2705       {
2706          // Rewind to start of (? sequence:
2707          --m_position;
2708          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2709          fail(regex_constants::error_paren, m_position - m_base);
2710          return false;
2711       }
2712    }
2713    while(!breakout);
2714
2715    breakout = false;
2716
2717    if(*m_position == static_cast<charT>('-'))
2718    {
2719       if(++m_position == m_end)
2720       {
2721          // Rewind to start of (? sequence:
2722          --m_position;
2723          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2724          fail(regex_constants::error_paren, m_position - m_base);
2725          return false;
2726       }
2727       do
2728       {
2729          switch(*m_position)
2730          {
2731          case 's':
2732             f &= ~regex_constants::mod_s;
2733             f |= regex_constants::no_mod_s;
2734             break;
2735          case 'm':
2736             f |= regex_constants::no_mod_m;
2737             break;
2738          case 'i':
2739             f &= ~regex_constants::icase;
2740             break;
2741          case 'x':
2742             f &= ~regex_constants::mod_x;
2743             break;
2744          default:
2745             breakout = true;
2746             continue;
2747          }
2748          if(++m_position == m_end)
2749          {
2750             // Rewind to start of (? sequence:
2751             --m_position;
2752             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2753             fail(regex_constants::error_paren, m_position - m_base);
2754             return false;
2755          }
2756       }
2757       while(!breakout);
2758    }
2759    return f;
2760 }
2761
2762 template <class charT, class traits>
2763 bool basic_regex_parser<charT, traits>::unwind_alts(std::ptrdiff_t last_paren_start)
2764 {
2765    //
2766    // If we didn't actually add any states after the last
2767    // alternative then that's an error:
2768    //
2769    if((this->m_alt_insert_point == static_cast<std::ptrdiff_t>(this->m_pdata->m_data.size()))
2770       && m_alt_jumps.size() && (m_alt_jumps.back() > last_paren_start)
2771       &&
2772       !(
2773          ((this->flags() & regbase::main_option_type) == regbase::perl_syntax_group)
2774            &&
2775          ((this->flags() & regbase::no_empty_expressions) == 0)
2776         )
2777       )
2778    {
2779       fail(regex_constants::error_empty, this->m_position - this->m_base, "Can't terminate a sub-expression with an alternation operator |.");
2780       return false;
2781    }
2782    //
2783    // Fix up our alternatives:
2784    //
2785    while(m_alt_jumps.size() && (m_alt_jumps.back() > last_paren_start))
2786    {
2787       //
2788       // fix up the jump to point to the end of the states
2789       // that we've just added:
2790       //
2791       std::ptrdiff_t jump_offset = m_alt_jumps.back();
2792       m_alt_jumps.pop_back();
2793       this->m_pdata->m_data.align();
2794       re_jump* jmp = static_cast<re_jump*>(this->getaddress(jump_offset));
2795       BOOST_ASSERT(jmp->type == syntax_element_jump);
2796       jmp->alt.i = this->m_pdata->m_data.size() - jump_offset;
2797    }
2798    return true;
2799 }
2800
2801 #ifdef BOOST_MSVC
2802 #pragma warning(pop)
2803 #endif
2804
2805 } // namespace re_detail
2806 } // namespace boost
2807
2808 #ifdef BOOST_MSVC
2809 #pragma warning(push)
2810 #pragma warning(disable: 4103)
2811 #endif
2812 #ifdef BOOST_HAS_ABI_HEADERS
2813 #  include BOOST_ABI_SUFFIX
2814 #endif
2815 #ifdef BOOST_MSVC
2816 #pragma warning(pop)
2817 #endif
2818
2819 #endif