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((m_position != m_end)
 945          && (0 == (this->flags() & regbase::main_option_type))
 946          && (this->m_traits.syntax_type(*m_position) == regex_constants::syntax_plus))
 947       {
 948          pocessive = true;
 949          ++m_position;
 950       }
 951    }
 952    if(0 == this->m_last_state)
 953    {
 954       fail(regex_constants::error_badrepeat, ::boost::re_detail::distance(m_base, m_position), "Nothing to repeat.");
 955       return false;
 956    }
 957    if(this->m_last_state->type == syntax_element_endmark)
 958    {
 959       // insert a repeat before the '(' matching the last ')':
 960       insert_point = this->m_paren_start;
 961    }
 962    else if((this->m_last_state->type == syntax_element_literal) && (static_cast<re_literal*>(this->m_last_state)->length > 1))
 963    {
 964       // the last state was a literal with more than one character, split it in two:
 965       re_literal* lit = static_cast<re_literal*>(this->m_last_state);
 966       charT c = (static_cast<charT*>(static_cast<void*>(lit+1)))[lit->length - 1];
 967       --(lit->length);
 968       // now append new state:
 969       lit = static_cast<re_literal*>(this->append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
 970       lit->length = 1;
 971       (static_cast<charT*>(static_cast<void*>(lit+1)))[0] = c;
 972       insert_point = this->getoffset(this->m_last_state);
 973    }
 974    else
 975    {
 976       // repeat the last state whatever it was, need to add some error checking here:
 977       switch(this->m_last_state->type)
 978       {
 979       case syntax_element_start_line:
 980       case syntax_element_end_line:
 981       case syntax_element_word_boundary:
 982       case syntax_element_within_word:
 983       case syntax_element_word_start:
 984       case syntax_element_word_end:
 985       case syntax_element_buffer_start:
 986       case syntax_element_buffer_end:
 987       case syntax_element_alt:
 988       case syntax_element_soft_buffer_end:
 989       case syntax_element_restart_continue:
 990       case syntax_element_jump:
 991       case syntax_element_startmark:
 992       case syntax_element_backstep:
 993          // can't legally repeat any of the above:
 994          fail(regex_constants::error_badrepeat, m_position - m_base);
 995          return false;
 996       default:
 997          // do nothing...
 998          break;
 999       }
1000       insert_point = this->getoffset(this->m_last_state);
1001    }
1002    //
1003    // OK we now know what to repeat, so insert the repeat around it:
1004    //
1005    re_repeat* rep = static_cast<re_repeat*>(this->insert_state(insert_point, syntax_element_rep, re_repeater_size));
1006    rep->min = low;
1007    rep->max = high;
1008    rep->greedy = greedy;
1009    rep->leading = false;
1010    // store our repeater position for later:
1011    std::ptrdiff_t rep_off = this->getoffset(rep);
1012    // and append a back jump to the repeat:
1013    re_jump* jmp = static_cast<re_jump*>(this->append_state(syntax_element_jump, sizeof(re_jump)));
1014    jmp->alt.i = rep_off - this->getoffset(jmp);
1015    this->m_pdata->m_data.align();
1016    // now fill in the alt jump for the repeat:
1017    rep = static_cast<re_repeat*>(this->getaddress(rep_off));
1018    rep->alt.i = this->m_pdata->m_data.size() - rep_off;
1019    //
1020    // If the repeat is pocessive then bracket the repeat with a (?>...)
1021    // independent sub-expression construct:
1022    //
1023    if(pocessive)
1024    {
1025       if(m_position != m_end)
1026       {
1027          //
1028          // Check for illegal following quantifier, we have to do this here, because
1029          // the extra states we insert below circumvents our usual error checking :-(
1030          //
1031          switch(this->m_traits.syntax_type(*m_position))
1032          {
1033          case regex_constants::syntax_star:
1034          case regex_constants::syntax_plus:
1035          case regex_constants::syntax_question:
1036          case regex_constants::syntax_open_brace:
1037             fail(regex_constants::error_badrepeat, m_position - m_base);
1038             return false;
1039          }
1040       }
1041       re_brace* pb = static_cast<re_brace*>(this->insert_state(insert_point, syntax_element_startmark, sizeof(re_brace)));
1042       pb->index = -3;
1043       pb->icase = this->flags() & regbase::icase;
1044       jmp = static_cast<re_jump*>(this->insert_state(insert_point + sizeof(re_brace), syntax_element_jump, sizeof(re_jump)));
1045       this->m_pdata->m_data.align();
1046       jmp->alt.i = this->m_pdata->m_data.size() - this->getoffset(jmp);
1047       pb = static_cast<re_brace*>(this->append_state(syntax_element_endmark, sizeof(re_brace)));
1048       pb->index = -3;
1049       pb->icase = this->flags() & regbase::icase;
1050    }
1051    return true;
1052 }
1053
1054 template <class charT, class traits>
1055 bool basic_regex_parser<charT, traits>::parse_repeat_range(bool isbasic)
1056 {
1057    static const char* incomplete_message = "Missing } in quantified repetition.";
1058    //
1059    // parse a repeat-range:
1060    //
1061    std::size_t min, max;
1062    int v;
1063    // skip whitespace:
1064    while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1065       ++m_position;
1066    // fail if at end:
1067    if(this->m_position == this->m_end)
1068    {
1069       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1070       return false;
1071    }
1072    // get min:
1073    v = this->m_traits.toi(m_position, m_end, 10);
1074    // skip whitespace:
1075    while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1076       ++m_position;
1077    if(v < 0)
1078    {
1079       fail(regex_constants::error_badbrace, this->m_position - this->m_base);
1080       return false;
1081    }
1082    else if(this->m_position == this->m_end)
1083    {
1084       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1085       return false;
1086    }
1087    min = v;
1088    // see if we have a comma:
1089    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_comma)
1090    {
1091       // move on and error check:
1092       ++m_position;
1093       // skip whitespace:
1094       while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1095          ++m_position;
1096       if(this->m_position == this->m_end)
1097       {
1098          fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1099          return false;
1100       }
1101       // get the value if any:
1102       v = this->m_traits.toi(m_position, m_end, 10);
1103       max = (v >= 0) ? v : (std::numeric_limits<std::size_t>::max)();
1104    }
1105    else
1106    {
1107       // no comma, max = min:
1108       max = min;
1109    }
1110    // skip whitespace:
1111    while((m_position != m_end) && this->m_traits.isctype(*m_position, this->m_mask_space))
1112       ++m_position;
1113    // OK now check trailing }:
1114    if(this->m_position == this->m_end)
1115    {
1116       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1117       return false;
1118    }
1119    if(isbasic)
1120    {
1121       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_escape)
1122       {
1123          ++m_position;
1124          if(this->m_position == this->m_end)
1125          {
1126             fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1127             return false;
1128          }
1129       }
1130       else
1131       {
1132          fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1133          return false;
1134       }
1135    }
1136    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_brace)
1137       ++m_position;
1138    else
1139    {
1140       fail(regex_constants::error_brace, this->m_position - this->m_base, incomplete_message);
1141       return false;
1142    }
1143    //
1144    // finally go and add the repeat, unless error:
1145    //
1146    if(min > max)
1147    {
1148       // Backtrack to error location:
1149       m_position -= 2;
1150       while(this->m_traits.isctype(*m_position, this->m_word_mask)) --m_position;
1151          ++m_position;
1152       fail(regex_constants::error_badbrace, m_position - m_base);
1153       return false;
1154    }
1155    return parse_repeat(min, max);
1156 }
1157
1158 template <class charT, class traits>
1159 bool basic_regex_parser<charT, traits>::parse_alt()
1160 {
1161    //
1162    // error check: if there have been no previous states,
1163    // or if the last state was a '(' then error:
1164    //
1165    if(
1166       ((this->m_last_state == 0) || (this->m_last_state->type == syntax_element_startmark))
1167       &&
1168       !(
1169          ((this->flags() & regbase::main_option_type) == regbase::perl_syntax_group)
1170            &&
1171          ((this->flags() & regbase::no_empty_expressions) == 0)
1172         )
1173       )
1174    {
1175       fail(regex_constants::error_empty, this->m_position - this->m_base, "A regular expression can start with the alternation operator |.");
1176       return false;
1177    }
1178    //
1179    // Reset mark count if required:
1180    //
1181    if(m_max_mark < m_mark_count)
1182       m_max_mark = m_mark_count;
1183    if(m_mark_reset >= 0)
1184       m_mark_count = m_mark_reset;
1185
1186    ++m_position;
1187    //
1188    // we need to append a trailing jump:
1189    //
1190    re_syntax_base* pj = this->append_state(re_detail::syntax_element_jump, sizeof(re_jump));
1191    std::ptrdiff_t jump_offset = this->getoffset(pj);
1192    //
1193    // now insert the alternative:
1194    //
1195    re_alt* palt = static_cast<re_alt*>(this->insert_state(this->m_alt_insert_point, syntax_element_alt, re_alt_size));
1196    jump_offset += re_alt_size;
1197    this->m_pdata->m_data.align();
1198    palt->alt.i = this->m_pdata->m_data.size() - this->getoffset(palt);
1199    //
1200    // update m_alt_insert_point so that the next alternate gets
1201    // inserted at the start of the second of the two we've just created:
1202    //
1203    this->m_alt_insert_point = this->m_pdata->m_data.size();
1204    //
1205    // the start of this alternative must have a case changes state
1206    // if the current block has messed around with case changes:
1207    //
1208    if(m_has_case_change)
1209    {
1210       static_cast<re_case*>(
1211          this->append_state(syntax_element_toggle_case, sizeof(re_case))
1212          )->icase = this->m_icase;
1213    }
1214    //
1215    // push the alternative onto our stack, a recursive
1216    // implementation here is easier to understand (and faster
1217    // as it happens), but causes all kinds of stack overflow problems
1218    // on programs with small stacks (COM+).
1219    //
1220    m_alt_jumps.push_back(jump_offset);
1221    return true;
1222 }
1223
1224 template <class charT, class traits>
1225 bool basic_regex_parser<charT, traits>::parse_set()
1226 {
1227    static const char* incomplete_message = "Character set declaration starting with [ terminated prematurely - either no ] was found or the set had no content.";
1228    ++m_position;
1229    if(m_position == m_end)
1230    {
1231       fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1232       return false;
1233    }
1234    basic_char_set<charT, traits> char_set;
1235
1236    const charT* base = m_position;  // where the '[' was
1237    const charT* item_base = m_position;  // where the '[' or '^' was
1238
1239    while(m_position != m_end)
1240    {
1241       switch(this->m_traits.syntax_type(*m_position))
1242       {
1243       case regex_constants::syntax_caret:
1244          if(m_position == base)
1245          {
1246             char_set.negate();
1247             ++m_position;
1248             item_base = m_position;
1249          }
1250          else
1251             parse_set_literal(char_set);
1252          break;
1253       case regex_constants::syntax_close_set:
1254          if(m_position == item_base)
1255          {
1256             parse_set_literal(char_set);
1257             break;
1258          }
1259          else
1260          {
1261             ++m_position;
1262             if(0 == this->append_set(char_set))
1263             {
1264                fail(regex_constants::error_ctype, m_position - m_base);
1265                return false;
1266             }
1267          }
1268          return true;
1269       case regex_constants::syntax_open_set:
1270          if(parse_inner_set(char_set))
1271             break;
1272          return true;
1273       case regex_constants::syntax_escape:
1274          {
1275             //
1276             // look ahead and see if this is a character class shortcut
1277             // \d \w \s etc...
1278             //
1279             ++m_position;
1280             if(this->m_traits.escape_syntax_type(*m_position)
1281                == regex_constants::escape_type_class)
1282             {
1283                char_class_type m = this->m_traits.lookup_classname(m_position, m_position+1);
1284                if(m != 0)
1285                {
1286                   char_set.add_class(m);
1287                   ++m_position;
1288                   break;
1289                }
1290             }
1291             else if(this->m_traits.escape_syntax_type(*m_position)
1292                == regex_constants::escape_type_not_class)
1293             {
1294                // negated character class:
1295                char_class_type m = this->m_traits.lookup_classname(m_position, m_position+1);
1296                if(m != 0)
1297                {
1298                   char_set.add_negated_class(m);
1299                   ++m_position;
1300                   break;
1301                }
1302             }
1303             // not a character class, just a regular escape:
1304             --m_position;
1305             parse_set_literal(char_set);
1306             break;
1307          }
1308       default:
1309          parse_set_literal(char_set);
1310          break;
1311       }
1312    }
1313    return m_position != m_end;
1314 }
1315
1316 template <class charT, class traits>
1317 bool basic_regex_parser<charT, traits>::parse_inner_set(basic_char_set<charT, traits>& char_set)
1318 {
1319    static const char* incomplete_message = "Character class declaration starting with [ terminated prematurely - either no ] was found or the set had no content.";
1320    //
1321    // we have either a character class [:name:]
1322    // a collating element [.name.]
1323    // or an equivalence class [=name=]
1324    //
1325    if(m_end == ++m_position)
1326    {
1327       fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1328       return false;
1329    }
1330    switch(this->m_traits.syntax_type(*m_position))
1331    {
1332    case regex_constants::syntax_dot:
1333       //
1334       // a collating element is treated as a literal:
1335       //
1336       --m_position;
1337       parse_set_literal(char_set);
1338       return true;
1339    case regex_constants::syntax_colon:
1340       {
1341       // check that character classes are actually enabled:
1342       if((this->flags() & (regbase::main_option_type | regbase::no_char_classes))
1343          == (regbase::basic_syntax_group  | regbase::no_char_classes))
1344       {
1345          --m_position;
1346          parse_set_literal(char_set);
1347          return true;
1348       }
1349       // skip the ':'
1350       if(m_end == ++m_position)
1351       {
1352          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1353          return false;
1354       }
1355       const charT* name_first = m_position;
1356       // skip at least one character, then find the matching ':]'
1357       if(m_end == ++m_position)
1358       {
1359          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1360          return false;
1361       }
1362       while((m_position != m_end)
1363          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_colon))
1364          ++m_position;
1365       const charT* name_last = m_position;
1366       if(m_end == m_position)
1367       {
1368          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1369          return false;
1370       }
1371       if((m_end == ++m_position)
1372          || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1373       {
1374          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1375          return false;
1376       }
1377       //
1378       // check for negated class:
1379       //
1380       bool negated = false;
1381       if(this->m_traits.syntax_type(*name_first) == regex_constants::syntax_caret)
1382       {
1383          ++name_first;
1384          negated = true;
1385       }
1386       typedef typename traits::char_class_type mask_type;
1387       mask_type m = this->m_traits.lookup_classname(name_first, name_last);
1388       if(m == 0)
1389       {
1390          if(char_set.empty() && (name_last - name_first == 1))
1391          {
1392             // maybe a special case:
1393             ++m_position;
1394             if( (m_position != m_end)
1395                && (this->m_traits.syntax_type(*m_position)
1396                   == regex_constants::syntax_close_set))
1397             {
1398                if(this->m_traits.escape_syntax_type(*name_first)
1399                   == regex_constants::escape_type_left_word)
1400                {
1401                   ++m_position;
1402                   this->append_state(syntax_element_word_start);
1403                   return false;
1404                }
1405                if(this->m_traits.escape_syntax_type(*name_first)
1406                   == regex_constants::escape_type_right_word)
1407                {
1408                   ++m_position;
1409                   this->append_state(syntax_element_word_end);
1410                   return false;
1411                }
1412             }
1413          }
1414          fail(regex_constants::error_ctype, name_first - m_base);
1415          return false;
1416       }
1417       if(negated == false)
1418          char_set.add_class(m);
1419       else
1420          char_set.add_negated_class(m);
1421       ++m_position;
1422       break;
1423    }
1424    case regex_constants::syntax_equal:
1425       {
1426       // skip the '='
1427       if(m_end == ++m_position)
1428       {
1429          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1430          return false;
1431       }
1432       const charT* name_first = m_position;
1433       // skip at least one character, then find the matching '=]'
1434       if(m_end == ++m_position)
1435       {
1436          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1437          return false;
1438       }
1439       while((m_position != m_end)
1440          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_equal))
1441          ++m_position;
1442       const charT* name_last = m_position;
1443       if(m_end == m_position)
1444       {
1445          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1446          return false;
1447       }
1448       if((m_end == ++m_position)
1449          || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1450       {
1451          fail(regex_constants::error_brack, m_position - m_base, incomplete_message);
1452          return false;
1453       }
1454       string_type m = this->m_traits.lookup_collatename(name_first, name_last);
1455       if((0 == m.size()) || (m.size() > 2))
1456       {
1457          fail(regex_constants::error_collate, name_first - m_base);
1458          return false;
1459       }
1460       digraph<charT> d;
1461       d.first = m[0];
1462       if(m.size() > 1)
1463          d.second = m[1];
1464       else
1465          d.second = 0;
1466       char_set.add_equivalent(d);
1467       ++m_position;
1468       break;
1469    }
1470    default:
1471       --m_position;
1472       parse_set_literal(char_set);
1473       break;
1474    }
1475    return true;
1476 }
1477
1478 template <class charT, class traits>
1479 void basic_regex_parser<charT, traits>::parse_set_literal(basic_char_set<charT, traits>& char_set)
1480 {
1481    digraph<charT> start_range(get_next_set_literal(char_set));
1482    if(m_end == m_position)
1483    {
1484       fail(regex_constants::error_brack, m_position - m_base);
1485       return;
1486    }
1487    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_dash)
1488    {
1489       // we have a range:
1490       if(m_end == ++m_position)
1491       {
1492          fail(regex_constants::error_brack, m_position - m_base);
1493          return;
1494       }
1495       if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set)
1496       {
1497          digraph<charT> end_range = get_next_set_literal(char_set);
1498          char_set.add_range(start_range, end_range);
1499          if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_dash)
1500          {
1501             if(m_end == ++m_position)
1502             {
1503                fail(regex_constants::error_brack, m_position - m_base);
1504                return;
1505             }
1506             if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_set)
1507             {
1508                // trailing - :
1509                --m_position;
1510                return;
1511             }
1512             fail(regex_constants::error_range, m_position - m_base);
1513             return;
1514          }
1515          return;
1516       }
1517       --m_position;
1518    }
1519    char_set.add_single(start_range);
1520 }
1521
1522 template <class charT, class traits>
1523 digraph<charT> basic_regex_parser<charT, traits>::get_next_set_literal(basic_char_set<charT, traits>& char_set)
1524 {
1525    digraph<charT> result;
1526    switch(this->m_traits.syntax_type(*m_position))
1527    {
1528    case regex_constants::syntax_dash:
1529       if(!char_set.empty())
1530       {
1531          // see if we are at the end of the set:
1532          if((++m_position == m_end) || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1533          {
1534             fail(regex_constants::error_range, m_position - m_base);
1535             return result;
1536          }
1537          --m_position;
1538       }
1539       result.first = *m_position++;
1540       return result;
1541    case regex_constants::syntax_escape:
1542       // check to see if escapes are supported first:
1543       if(this->flags() & regex_constants::no_escape_in_lists)
1544       {
1545          result = *m_position++;
1546          break;
1547       }
1548       ++m_position;
1549       result = unescape_character();
1550       break;
1551    case regex_constants::syntax_open_set:
1552    {
1553       if(m_end == ++m_position)
1554       {
1555          fail(regex_constants::error_collate, m_position - m_base);
1556          return result;
1557       }
1558       if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_dot)
1559       {
1560          --m_position;
1561          result.first = *m_position;
1562          ++m_position;
1563          return result;
1564       }
1565       if(m_end == ++m_position)
1566       {
1567          fail(regex_constants::error_collate, m_position - m_base);
1568          return result;
1569       }
1570       const charT* name_first = m_position;
1571       // skip at least one character, then find the matching ':]'
1572       if(m_end == ++m_position)
1573       {
1574          fail(regex_constants::error_collate, name_first - m_base);
1575          return result;
1576       }
1577       while((m_position != m_end)
1578          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_dot))
1579          ++m_position;
1580       const charT* name_last = m_position;
1581       if(m_end == m_position)
1582       {
1583          fail(regex_constants::error_collate, name_first - m_base);
1584          return result;
1585       }
1586       if((m_end == ++m_position)
1587          || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_set))
1588       {
1589          fail(regex_constants::error_collate, name_first - m_base);
1590          return result;
1591       }
1592       ++m_position;
1593       string_type s = this->m_traits.lookup_collatename(name_first, name_last);
1594       if(s.empty() || (s.size() > 2))
1595       {
1596          fail(regex_constants::error_collate, name_first - m_base);
1597          return result;
1598       }
1599       result.first = s[0];
1600       if(s.size() > 1)
1601          result.second = s[1];
1602       else
1603          result.second = 0;
1604       return result;
1605    }
1606    default:
1607       result = *m_position++;
1608    }
1609    return result;
1610 }
1611
1612 //
1613 // does a value fit in the specified charT type?
1614 //
1615 template <class charT>
1616 bool valid_value(charT, int v, const mpl::true_&)
1617 {
1618    return (v >> (sizeof(charT) * CHAR_BIT)) == 0;
1619 }
1620 template <class charT>
1621 bool valid_value(charT, int, const mpl::false_&)
1622 {
1623    return true; // v will alsways fit in a charT
1624 }
1625 template <class charT>
1626 bool valid_value(charT c, int v)
1627 {
1628    return valid_value(c, v, mpl::bool_<(sizeof(charT) < sizeof(int))>());
1629 }
1630
1631 template <class charT, class traits>
1632 charT basic_regex_parser<charT, traits>::unescape_character()
1633 {
1634 #ifdef BOOST_MSVC
1635 #pragma warning(push)
1636 #pragma warning(disable:4127)
1637 #endif
1638    charT result(0);
1639    if(m_position == m_end)
1640    {
1641       fail(regex_constants::error_escape, m_position - m_base, "Escape sequence terminated prematurely.");
1642       return false;
1643    }
1644    switch(this->m_traits.escape_syntax_type(*m_position))
1645    {
1646    case regex_constants::escape_type_control_a:
1647       result = charT('\a');
1648       break;
1649    case regex_constants::escape_type_e:
1650       result = charT(27);
1651       break;
1652    case regex_constants::escape_type_control_f:
1653       result = charT('\f');
1654       break;
1655    case regex_constants::escape_type_control_n:
1656       result = charT('\n');
1657       break;
1658    case regex_constants::escape_type_control_r:
1659       result = charT('\r');
1660       break;
1661    case regex_constants::escape_type_control_t:
1662       result = charT('\t');
1663       break;
1664    case regex_constants::escape_type_control_v:
1665       result = charT('\v');
1666       break;
1667    case regex_constants::escape_type_word_assert:
1668       result = charT('\b');
1669       break;
1670    case regex_constants::escape_type_ascii_control:
1671       ++m_position;
1672       if(m_position == m_end)
1673       {
1674          // Rewind to start of escape:
1675          --m_position;
1676          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1677          fail(regex_constants::error_escape, m_position - m_base, "ASCII escape sequence terminated prematurely.");
1678          return result;
1679       }
1680       result = static_cast<charT>(*m_position % 32);
1681       break;
1682    case regex_constants::escape_type_hex:
1683       ++m_position;
1684       if(m_position == m_end)
1685       {
1686          // Rewind to start of escape:
1687          --m_position;
1688          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1689          fail(regex_constants::error_escape, m_position - m_base, "Hexadecimal escape sequence terminated prematurely.");
1690          return result;
1691       }
1692       // maybe have \x{ddd}
1693       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_open_brace)
1694       {
1695          ++m_position;
1696          if(m_position == m_end)
1697          {
1698             // Rewind to start of escape:
1699             --m_position;
1700             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1701             fail(regex_constants::error_escape, m_position - m_base, "Missing } in hexadecimal escape sequence.");
1702             return result;
1703          }
1704          int i = this->m_traits.toi(m_position, m_end, 16);
1705          if((m_position == m_end)
1706             || (i < 0)
1707             || ((std::numeric_limits<charT>::is_specialized) && (i > (int)(std::numeric_limits<charT>::max)()))
1708             || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_brace))
1709          {
1710             // Rewind to start of escape:
1711             --m_position;
1712             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1713             fail(regex_constants::error_badbrace, m_position - m_base, "Hexadecimal escape sequence was invalid.");
1714             return result;
1715          }
1716          ++m_position;
1717          result = charT(i);
1718       }
1719       else
1720       {
1721          std::ptrdiff_t len = (std::min)(static_cast<std::ptrdiff_t>(2), static_cast<std::ptrdiff_t>(m_end - m_position));
1722          int i = this->m_traits.toi(m_position, m_position + len, 16);
1723          if((i < 0)
1724             || !valid_value(charT(0), i))
1725          {
1726             // Rewind to start of escape:
1727             --m_position;
1728             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1729             fail(regex_constants::error_escape, m_position - m_base, "Escape sequence did not encode a valid character.");
1730             return result;
1731          }
1732          result = charT(i);
1733       }
1734       return result;
1735    case regex_constants::syntax_digit:
1736       {
1737       // an octal escape sequence, the first character must be a zero
1738       // followed by up to 3 octal digits:
1739       std::ptrdiff_t len = (std::min)(::boost::re_detail::distance(m_position, m_end), static_cast<std::ptrdiff_t>(4));
1740       const charT* bp = m_position;
1741       int val = this->m_traits.toi(bp, bp + 1, 8);
1742       if(val != 0)
1743       {
1744          // Rewind to start of escape:
1745          --m_position;
1746          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1747          // Oops not an octal escape after all:
1748          fail(regex_constants::error_escape, m_position - m_base, "Invalid octal escape sequence.");
1749          return result;
1750       }
1751       val = this->m_traits.toi(m_position, m_position + len, 8);
1752       if(val < 0)
1753       {
1754          // Rewind to start of escape:
1755          --m_position;
1756          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1757          fail(regex_constants::error_escape, m_position - m_base, "Octal escape sequence is invalid.");
1758          return result;
1759       }
1760       return static_cast<charT>(val);
1761       }
1762    case regex_constants::escape_type_named_char:
1763       {
1764          ++m_position;
1765          if(m_position == m_end)
1766          {
1767             // Rewind to start of escape:
1768             --m_position;
1769             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1770             fail(regex_constants::error_escape, m_position - m_base);
1771             return false;
1772          }
1773          // maybe have \N{name}
1774          if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_open_brace)
1775          {
1776             const charT* base = m_position;
1777             // skip forward until we find enclosing brace:
1778             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_brace))
1779                ++m_position;
1780             if(m_position == m_end)
1781             {
1782                // Rewind to start of escape:
1783                --m_position;
1784                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1785                fail(regex_constants::error_escape, m_position - m_base);
1786                return false;
1787             }
1788             string_type s = this->m_traits.lookup_collatename(++base, m_position++);
1789             if(s.empty())
1790             {
1791                // Rewind to start of escape:
1792                --m_position;
1793                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1794                fail(regex_constants::error_collate, m_position - m_base);
1795                return false;
1796             }
1797             if(s.size() == 1)
1798             {
1799                return s[0];
1800             }
1801          }
1802          // fall through is a failure:
1803          // Rewind to start of escape:
1804          --m_position;
1805          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1806          fail(regex_constants::error_escape, m_position - m_base);
1807          return false;
1808       }
1809    default:
1810       result = *m_position;
1811       break;
1812    }
1813    ++m_position;
1814    return result;
1815 #ifdef BOOST_MSVC
1816 #pragma warning(pop)
1817 #endif
1818 }
1819
1820 template <class charT, class traits>
1821 bool basic_regex_parser<charT, traits>::parse_backref()
1822 {
1823    BOOST_ASSERT(m_position != m_end);
1824    const charT* pc = m_position;
1825    int i = this->m_traits.toi(pc, pc + 1, 10);
1826    if((i == 0) || (((this->flags() & regbase::main_option_type) == regbase::perl_syntax_group) && (this->flags() & regbase::no_bk_refs)))
1827    {
1828       // not a backref at all but an octal escape sequence:
1829       charT c = unescape_character();
1830       this->append_literal(c);
1831    }
1832    else if((i > 0) && (this->m_backrefs & (1u << (i-1))))
1833    {
1834       m_position = pc;
1835       re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_backref, sizeof(re_brace)));
1836       pb->index = i;
1837       pb->icase = this->flags() & regbase::icase;
1838    }
1839    else
1840    {
1841       // Rewind to start of escape:
1842       --m_position;
1843       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
1844       fail(regex_constants::error_backref, m_position - m_base);
1845       return false;
1846    }
1847    return true;
1848 }
1849
1850 template <class charT, class traits>
1851 bool basic_regex_parser<charT, traits>::parse_QE()
1852 {
1853 #ifdef BOOST_MSVC
1854 #pragma warning(push)
1855 #pragma warning(disable:4127)
1856 #endif
1857    //
1858    // parse a \Q...\E sequence:
1859    //
1860    ++m_position; // skip the Q
1861    const charT* start = m_position;
1862    const charT* end;
1863    do
1864    {
1865       while((m_position != m_end)
1866          && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape))
1867          ++m_position;
1868       if(m_position == m_end)
1869       {
1870          //  a \Q...\E sequence may terminate with the end of the expression:
1871          end = m_position;
1872          break;
1873       }
1874       if(++m_position == m_end) // skip the escape
1875       {
1876          fail(regex_constants::error_escape, m_position - m_base, "Unterminated \\Q...\\E sequence.");
1877          return false;
1878       }
1879       // check to see if it's a \E:
1880       if(this->m_traits.escape_syntax_type(*m_position) == regex_constants::escape_type_E)
1881       {
1882          ++m_position;
1883          end = m_position - 2;
1884          break;
1885       }
1886       // otherwise go round again:
1887    }while(true);
1888    //
1889    // now add all the character between the two escapes as literals:
1890    //
1891    while(start != end)
1892    {
1893       this->append_literal(*start);
1894       ++start;
1895    }
1896    return true;
1897 #ifdef BOOST_MSVC
1898 #pragma warning(pop)
1899 #endif
1900 }
1901
1902 template <class charT, class traits>
1903 bool basic_regex_parser<charT, traits>::parse_perl_extension()
1904 {
1905    if(++m_position == m_end)
1906    {
1907       // Rewind to start of (? sequence:
1908       --m_position;
1909       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
1910       fail(regex_constants::error_perl_extension, m_position - m_base);
1911       return false;
1912    }
1913    //
1914    // treat comments as a special case, as these
1915    // are the only ones that don't start with a leading
1916    // startmark state:
1917    //
1918    if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_hash)
1919    {
1920       while((m_position != m_end)
1921          && (this->m_traits.syntax_type(*m_position++) != regex_constants::syntax_close_mark))
1922       {}
1923       return true;
1924    }
1925    //
1926    // backup some state, and prepare the way:
1927    //
1928    int markid = 0;
1929    std::ptrdiff_t jump_offset = 0;
1930    re_brace* pb = static_cast<re_brace*>(this->append_state(syntax_element_startmark, sizeof(re_brace)));
1931    pb->icase = this->flags() & regbase::icase;
1932    std::ptrdiff_t last_paren_start = this->getoffset(pb);
1933    // back up insertion point for alternations, and set new point:
1934    std::ptrdiff_t last_alt_point = m_alt_insert_point;
1935    this->m_pdata->m_data.align();
1936    m_alt_insert_point = this->m_pdata->m_data.size();
1937    std::ptrdiff_t expected_alt_point = m_alt_insert_point;
1938    bool restore_flags = true;
1939    regex_constants::syntax_option_type old_flags = this->flags();
1940    bool old_case_change = m_has_case_change;
1941    m_has_case_change = false;
1942    charT name_delim;
1943    int mark_reset = m_mark_reset;
1944    int max_mark = m_max_mark;
1945    m_mark_reset = -1;
1946    m_max_mark = m_mark_count;
1947    int v;
1948    //
1949    // select the actual extension used:
1950    //
1951    switch(this->m_traits.syntax_type(*m_position))
1952    {
1953    case regex_constants::syntax_or:
1954       m_mark_reset = m_mark_count;
1955       // fall through:
1956    case regex_constants::syntax_colon:
1957       //
1958       // a non-capturing mark:
1959       //
1960       pb->index = markid = 0;
1961       ++m_position;
1962       break;
1963    case regex_constants::syntax_digit:
1964       {
1965       //
1966       // a recursive subexpression:
1967       //
1968       v = this->m_traits.toi(m_position, m_end, 10);
1969       if((v < 0) || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
1970       {
1971          // Rewind to start of (? sequence:
1972          --m_position;
1973          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
1974          fail(regex_constants::error_perl_extension, m_position - m_base, "The recursive sub-expression refers to an invalid marking group, or is unterminated.");
1975          return false;
1976       }
1977 insert_recursion:
1978       pb->index = markid = 0;
1979       re_recurse* pr = static_cast<re_recurse*>(this->append_state(syntax_element_recurse, sizeof(re_recurse)));
1980       pr->alt.i = v;
1981       pr->state_id = 0;
1982       static_cast<re_case*>(
1983             this->append_state(syntax_element_toggle_case, sizeof(re_case))
1984             )->icase = this->flags() & regbase::icase;
1985       break;
1986       }
1987    case regex_constants::syntax_plus:
1988       //
1989       // A forward-relative recursive subexpression:
1990       //
1991       ++m_position;
1992       v = this->m_traits.toi(m_position, m_end, 10);
1993       if((v <= 0) || (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
1994       {
1995          // Rewind to start of (? sequence:
1996          --m_position;
1997          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
1998          fail(regex_constants::error_perl_extension, m_position - m_base, "An invalid or unterminated recursive sub-expression.");
1999          return false;
2000       }
2001       v += m_mark_count;
2002       goto insert_recursion;
2003    case regex_constants::syntax_dash:
2004       //
2005       // Possibly a backward-relative recursive subexpression:
2006       //
2007       ++m_position;
2008       v = this->m_traits.toi(m_position, m_end, 10);
2009       if(v <= 0)
2010       {
2011          --m_position;
2012          // Oops not a relative recursion at all, but a (?-imsx) group:
2013          goto option_group_jump;
2014       }
2015       v = m_mark_count + 1 - v;
2016       if(v <= 0)
2017       {
2018          // Rewind to start of (? sequence:
2019          --m_position;
2020          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2021          fail(regex_constants::error_perl_extension, m_position - m_base, "An invalid or unterminated recursive sub-expression.");
2022          return false;
2023       }
2024       goto insert_recursion;
2025    case regex_constants::syntax_equal:
2026       pb->index = markid = -1;
2027       ++m_position;
2028       jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2029       this->m_pdata->m_data.align();
2030       m_alt_insert_point = this->m_pdata->m_data.size();
2031       break;
2032    case regex_constants::syntax_not:
2033       pb->index = markid = -2;
2034       ++m_position;
2035       jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2036       this->m_pdata->m_data.align();
2037       m_alt_insert_point = this->m_pdata->m_data.size();
2038       break;
2039    case regex_constants::escape_type_left_word:
2040       {
2041          // a lookbehind assertion:
2042          if(++m_position == m_end)
2043          {
2044             // Rewind to start of (? sequence:
2045             --m_position;
2046             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2047             fail(regex_constants::error_perl_extension, m_position - m_base);
2048             return false;
2049          }
2050          regex_constants::syntax_type t = this->m_traits.syntax_type(*m_position);
2051          if(t == regex_constants::syntax_not)
2052             pb->index = markid = -2;
2053          else if(t == regex_constants::syntax_equal)
2054             pb->index = markid = -1;
2055          else
2056          {
2057             // Probably a named capture which also starts (?< :
2058             name_delim = '>';
2059             --m_position;
2060             goto named_capture_jump;
2061          }
2062          ++m_position;
2063          jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2064          this->append_state(syntax_element_backstep, sizeof(re_brace));
2065          this->m_pdata->m_data.align();
2066          m_alt_insert_point = this->m_pdata->m_data.size();
2067          break;
2068       }
2069    case regex_constants::escape_type_right_word:
2070       //
2071       // an independent sub-expression:
2072       //
2073       pb->index = markid = -3;
2074       ++m_position;
2075       jump_offset = this->getoffset(this->append_state(syntax_element_jump, sizeof(re_jump)));
2076       this->m_pdata->m_data.align();
2077       m_alt_insert_point = this->m_pdata->m_data.size();
2078       break;
2079    case regex_constants::syntax_open_mark:
2080       {
2081       // a conditional expression:
2082       pb->index = markid = -4;
2083       if(++m_position == m_end)
2084       {
2085          // Rewind to start of (? sequence:
2086          --m_position;
2087          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2088          fail(regex_constants::error_perl_extension, m_position - m_base);
2089          return false;
2090       }
2091       v = this->m_traits.toi(m_position, m_end, 10);
2092       if(*m_position == charT('R'))
2093       {
2094          if(++m_position == m_end)
2095          {
2096             // Rewind to start of (? sequence:
2097             --m_position;
2098             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2099             fail(regex_constants::error_perl_extension, m_position - m_base);
2100             return false;
2101          }
2102          if(*m_position == charT('&'))
2103          {
2104             const charT* base = ++m_position;
2105             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
2106                ++m_position;
2107             if(m_position == m_end)
2108             {
2109                // Rewind to start of (? sequence:
2110                --m_position;
2111                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2112                fail(regex_constants::error_perl_extension, m_position - m_base);
2113                return false;
2114             }
2115             v = -static_cast<int>(hash_value_from_capture_name(base, m_position));
2116          }
2117          else
2118          {
2119             v = -this->m_traits.toi(m_position, m_end, 10);
2120          }
2121          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2122          br->index = v < 0 ? (v - 1) : 0;
2123          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2124          {
2125             // Rewind to start of (? sequence:
2126             --m_position;
2127             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2128             fail(regex_constants::error_perl_extension, m_position - m_base);
2129             return false;
2130          }
2131          if(++m_position == m_end)
2132          {
2133             // Rewind to start of (? sequence:
2134             --m_position;
2135             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2136             fail(regex_constants::error_perl_extension, m_position - m_base);
2137             return false;
2138          }
2139       }
2140       else if((*m_position == charT('\'')) || (*m_position == charT('<')))
2141       {
2142          const charT* base = ++m_position;
2143          while((m_position != m_end) && (*m_position != charT('>')) && (*m_position != charT('\'')))
2144             ++m_position;
2145          if(m_position == m_end)
2146          {
2147             // Rewind to start of (? sequence:
2148             --m_position;
2149             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2150             fail(regex_constants::error_perl_extension, m_position - m_base);
2151             return false;
2152          }
2153          v = static_cast<int>(hash_value_from_capture_name(base, m_position));
2154          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2155          br->index = v;
2156          if(((*m_position != charT('>')) && (*m_position != charT('\''))) || (++m_position == m_end))
2157          {
2158             // Rewind to start of (? sequence:
2159             --m_position;
2160             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2161             fail(regex_constants::error_perl_extension, m_position - m_base, "Unterminated named capture.");
2162             return false;
2163          }
2164          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2165          {
2166             // Rewind to start of (? sequence:
2167             --m_position;
2168             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2169             fail(regex_constants::error_perl_extension, m_position - m_base);
2170             return false;
2171          }
2172          if(++m_position == m_end)
2173          {
2174             // Rewind to start of (? sequence:
2175             --m_position;
2176             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2177             fail(regex_constants::error_perl_extension, m_position - m_base);
2178             return false;
2179          }
2180       }
2181       else if(*m_position == charT('D'))
2182       {
2183          const char* def = "DEFINE";
2184          while(*def && (m_position != m_end) && (*m_position == charT(*def)))
2185             ++m_position, ++def;
2186          if((m_position == m_end) || *def)
2187          {
2188             // Rewind to start of (? sequence:
2189             --m_position;
2190             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2191             fail(regex_constants::error_perl_extension, m_position - m_base);
2192             return false;
2193          }
2194          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2195          br->index = 9999; // special magic value!
2196          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2197          {
2198             // Rewind to start of (? sequence:
2199             --m_position;
2200             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2201             fail(regex_constants::error_perl_extension, m_position - m_base);
2202             return false;
2203          }
2204          if(++m_position == m_end)
2205          {
2206             // Rewind to start of (? sequence:
2207             --m_position;
2208             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2209             fail(regex_constants::error_perl_extension, m_position - m_base);
2210             return false;
2211          }
2212       }
2213       else if(v > 0)
2214       {
2215          re_brace* br = static_cast<re_brace*>(this->append_state(syntax_element_assert_backref, sizeof(re_brace)));
2216          br->index = v;
2217          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2218          {
2219             // Rewind to start of (? sequence:
2220             --m_position;
2221             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2222             fail(regex_constants::error_perl_extension, m_position - m_base);
2223             return false;
2224          }
2225          if(++m_position == m_end)
2226          {
2227             // Rewind to start of (? sequence:
2228             --m_position;
2229             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2230             fail(regex_constants::error_perl_extension, m_position - m_base);
2231             return false;
2232          }
2233       }
2234       else
2235       {
2236          // verify that we have a lookahead or lookbehind assert:
2237          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_question)
2238          {
2239             // Rewind to start of (? sequence:
2240             --m_position;
2241             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2242             fail(regex_constants::error_perl_extension, m_position - m_base);
2243             return false;
2244          }
2245          if(++m_position == m_end)
2246          {
2247             // Rewind to start of (? sequence:
2248             --m_position;
2249             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2250             fail(regex_constants::error_perl_extension, m_position - m_base);
2251             return false;
2252          }
2253          if(this->m_traits.syntax_type(*m_position) == regex_constants::escape_type_left_word)
2254          {
2255             if(++m_position == m_end)
2256             {
2257                // Rewind to start of (? sequence:
2258                --m_position;
2259                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2260                fail(regex_constants::error_perl_extension, m_position - m_base);
2261                return false;
2262             }
2263             if((this->m_traits.syntax_type(*m_position) != regex_constants::syntax_equal)
2264                && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_not))
2265             {
2266                // Rewind to start of (? sequence:
2267                --m_position;
2268                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2269                fail(regex_constants::error_perl_extension, m_position - m_base);
2270                return false;
2271             }
2272             m_position -= 3;
2273          }
2274          else
2275          {
2276             if((this->m_traits.syntax_type(*m_position) != regex_constants::syntax_equal)
2277                && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_not))
2278             {
2279                // Rewind to start of (? sequence:
2280                --m_position;
2281                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2282                fail(regex_constants::error_perl_extension, m_position - m_base);
2283                return false;
2284             }
2285             m_position -= 2;
2286          }
2287       }
2288       break;
2289       }
2290    case regex_constants::syntax_close_mark:
2291       // Rewind to start of (? sequence:
2292       --m_position;
2293       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2294       fail(regex_constants::error_perl_extension, m_position - m_base);
2295       return false;
2296    case regex_constants::escape_type_end_buffer:
2297       {
2298       name_delim = *m_position;
2299 named_capture_jump:
2300       markid = 0;
2301       if(0 == (this->flags() & regbase::nosubs))
2302       {
2303          markid = ++m_mark_count;
2304    #ifndef BOOST_NO_STD_DISTANCE
2305          if(this->flags() & regbase::save_subexpression_location)
2306             this->m_pdata->m_subs.push_back(std::pair<std::size_t, std::size_t>(std::distance(m_base, m_position) - 2, 0));
2307    #else
2308          if(this->flags() & regbase::save_subexpression_location)
2309             this->m_pdata->m_subs.push_back(std::pair<std::size_t, std::size_t>((m_position - m_base) - 2, 0));
2310    #endif
2311       }
2312       pb->index = markid;
2313       const charT* base = ++m_position;
2314       if(m_position == m_end)
2315       {
2316          // Rewind to start of (? sequence:
2317          --m_position;
2318          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2319          fail(regex_constants::error_perl_extension, m_position - m_base);
2320          return false;
2321       }
2322       while((m_position != m_end) && (*m_position != name_delim))
2323          ++m_position;
2324       if(m_position == m_end)
2325       {
2326          // Rewind to start of (? sequence:
2327          --m_position;
2328          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2329          fail(regex_constants::error_perl_extension, m_position - m_base);
2330          return false;
2331       }
2332       this->m_pdata->set_name(base, m_position, markid);
2333       ++m_position;
2334       break;
2335       }
2336    default:
2337       if(*m_position == charT('R'))
2338       {
2339          ++m_position;
2340          v = 0;
2341          if(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark)
2342          {
2343             // Rewind to start of (? sequence:
2344             --m_position;
2345             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2346             fail(regex_constants::error_perl_extension, m_position - m_base);
2347             return false;
2348          }
2349          goto insert_recursion;
2350       }
2351       if(*m_position == charT('&'))
2352       {
2353          ++m_position;
2354          const charT* base = m_position;
2355          while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
2356             ++m_position;
2357          if(m_position == m_end)
2358          {
2359             // Rewind to start of (? sequence:
2360             --m_position;
2361             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2362             fail(regex_constants::error_perl_extension, m_position - m_base);
2363             return false;
2364          }
2365          v = static_cast<int>(hash_value_from_capture_name(base, m_position));
2366          goto insert_recursion;
2367       }
2368       if(*m_position == charT('P'))
2369       {
2370          ++m_position;
2371          if(m_position == m_end)
2372          {
2373             // Rewind to start of (? sequence:
2374             --m_position;
2375             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2376             fail(regex_constants::error_perl_extension, m_position - m_base);
2377             return false;
2378          }
2379          if(*m_position == charT('>'))
2380          {
2381             ++m_position;
2382             const charT* base = m_position;
2383             while((m_position != m_end) && (this->m_traits.syntax_type(*m_position) != regex_constants::syntax_close_mark))
2384                ++m_position;
2385             if(m_position == m_end)
2386             {
2387                // Rewind to start of (? sequence:
2388                --m_position;
2389                while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2390                fail(regex_constants::error_perl_extension, m_position - m_base);
2391                return false;
2392             }
2393             v = static_cast<int>(hash_value_from_capture_name(base, m_position));
2394             goto insert_recursion;
2395          }
2396       }
2397       //
2398       // lets assume that we have a (?imsx) group and try and parse it:
2399       //
2400 option_group_jump:
2401       regex_constants::syntax_option_type opts = parse_options();
2402       if(m_position == m_end)
2403       {
2404          // Rewind to start of (? sequence:
2405          --m_position;
2406          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2407          fail(regex_constants::error_perl_extension, m_position - m_base);
2408          return false;
2409       }
2410       // make a note of whether we have a case change:
2411       m_has_case_change = ((opts & regbase::icase) != (this->flags() & regbase::icase));
2412       pb->index = markid = 0;
2413       if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_mark)
2414       {
2415          // update flags and carry on as normal:
2416          this->flags(opts);
2417          restore_flags = false;
2418          old_case_change |= m_has_case_change; // defer end of scope by one ')'
2419       }
2420       else if(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_colon)
2421       {
2422          // update flags and carry on until the matching ')' is found:
2423          this->flags(opts);
2424          ++m_position;
2425       }
2426       else
2427       {
2428          // Rewind to start of (? sequence:
2429          --m_position;
2430          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2431          fail(regex_constants::error_perl_extension, m_position - m_base);
2432          return false;
2433       }
2434
2435       // finally append a case change state if we need it:
2436       if(m_has_case_change)
2437       {
2438          static_cast<re_case*>(
2439             this->append_state(syntax_element_toggle_case, sizeof(re_case))
2440             )->icase = opts & regbase::icase;
2441       }
2442
2443    }
2444    //
2445    // now recursively add more states, this will terminate when we get to a
2446    // matching ')' :
2447    //
2448    parse_all();
2449    //
2450    // Unwind alternatives:
2451    //
2452    if(0 == unwind_alts(last_paren_start))
2453    {
2454       // Rewind to start of (? sequence:
2455       --m_position;
2456       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2457       fail(regex_constants::error_perl_extension, m_position - m_base, "Invalid alternation operators within (?...) block.");
2458       return false;
2459    }
2460    //
2461    // we either have a ')' or we have run out of characters prematurely:
2462    //
2463    if(m_position == m_end)
2464    {
2465       // Rewind to start of (? sequence:
2466       --m_position;
2467       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2468       this->fail(regex_constants::error_paren, ::boost::re_detail::distance(m_base, m_end));
2469       return false;
2470    }
2471    BOOST_ASSERT(this->m_traits.syntax_type(*m_position) == regex_constants::syntax_close_mark);
2472    ++m_position;
2473    //
2474    // restore the flags:
2475    //
2476    if(restore_flags)
2477    {
2478       // append a case change state if we need it:
2479       if(m_has_case_change)
2480       {
2481          static_cast<re_case*>(
2482             this->append_state(syntax_element_toggle_case, sizeof(re_case))
2483             )->icase = old_flags & regbase::icase;
2484       }
2485       this->flags(old_flags);
2486    }
2487    //
2488    // set up the jump pointer if we have one:
2489    //
2490    if(jump_offset)
2491    {
2492       this->m_pdata->m_data.align();
2493       re_jump* jmp = static_cast<re_jump*>(this->getaddress(jump_offset));
2494       jmp->alt.i = this->m_pdata->m_data.size() - this->getoffset(jmp);
2495       if(this->m_last_state == jmp)
2496       {
2497          // Oops... we didn't have anything inside the assertion:
2498          // Rewind to start of (? sequence:
2499          --m_position;
2500          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2501          fail(regex_constants::error_perl_extension, m_position - m_base, "Invalid or empty zero width assertion.");
2502          return false;
2503       }
2504    }
2505    //
2506    // verify that if this is conditional expression, that we do have
2507    // an alternative, if not add one:
2508    //
2509    if(markid == -4)
2510    {
2511       re_syntax_base* b = this->getaddress(expected_alt_point);
2512       // Make sure we have exactly one alternative following this state:
2513       if(b->type != syntax_element_alt)
2514       {
2515          re_alt* alt = static_cast<re_alt*>(this->insert_state(expected_alt_point, syntax_element_alt, sizeof(re_alt)));
2516          alt->alt.i = this->m_pdata->m_data.size() - this->getoffset(alt);
2517       }
2518       else if(this->getaddress(static_cast<re_alt*>(b)->alt.i, b)->type == syntax_element_alt)
2519       {
2520          // Can't have seen more than one alternative:
2521          // Rewind to start of (? sequence:
2522          --m_position;
2523          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2524          fail(regex_constants::error_bad_pattern, m_position - m_base, "More than one alternation operator | was encountered inside a conditional expression.");
2525          return false;
2526       }
2527       else
2528       {
2529          // We must *not* have seen an alternative inside a (DEFINE) block:
2530          b = this->getaddress(b->next.i, b);
2531          if((b->type == syntax_element_assert_backref) && (static_cast<re_brace*>(b)->index == 9999))
2532          {
2533             // Rewind to start of (? sequence:
2534             --m_position;
2535             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2536             fail(regex_constants::error_bad_pattern, m_position - m_base, "Alternation operators are not allowed inside a DEFINE block.");
2537             return false;
2538          }
2539       }
2540       // check for invalid repetition of next state:
2541       b = this->getaddress(expected_alt_point);
2542       b = this->getaddress(static_cast<re_alt*>(b)->next.i, b);
2543       if((b->type != syntax_element_assert_backref)
2544          && (b->type != syntax_element_startmark))
2545       {
2546          // Rewind to start of (? sequence:
2547          --m_position;
2548          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2549          fail(regex_constants::error_badrepeat, m_position - m_base, "A repetition operator cannot be applied to a zero-width assertion.");
2550          return false;
2551       }
2552    }
2553    //
2554    // append closing parenthesis state:
2555    //
2556    pb = static_cast<re_brace*>(this->append_state(syntax_element_endmark, sizeof(re_brace)));
2557    pb->index = markid;
2558    pb->icase = this->flags() & regbase::icase;
2559    this->m_paren_start = last_paren_start;
2560    //
2561    // restore the alternate insertion point:
2562    //
2563    this->m_alt_insert_point = last_alt_point;
2564    //
2565    // and the case change data:
2566    //
2567    m_has_case_change = old_case_change;
2568    //
2569    // And the mark_reset data:
2570    //
2571    if(m_max_mark > m_mark_count)
2572    {
2573       m_mark_count = m_max_mark;
2574    }
2575    m_mark_reset = mark_reset;
2576    m_max_mark = max_mark;
2577
2578
2579    if(markid > 0)
2580    {
2581 #ifndef BOOST_NO_STD_DISTANCE
2582       if(this->flags() & regbase::save_subexpression_location)
2583          this->m_pdata->m_subs.at(markid - 1).second = std::distance(m_base, m_position) - 1;
2584 #else
2585       if(this->flags() & regbase::save_subexpression_location)
2586          this->m_pdata->m_subs.at(markid - 1).second = (m_position - m_base) - 1;
2587 #endif
2588       //
2589       // allow backrefs to this mark:
2590       //
2591       if((markid > 0) && (markid < (int)(sizeof(unsigned) * CHAR_BIT)))
2592          this->m_backrefs |= 1u << (markid - 1);
2593    }
2594    return true;
2595 }
2596
2597 template <class charT, class traits>
2598 bool basic_regex_parser<charT, traits>::add_emacs_code(bool negate)
2599 {
2600    //
2601    // parses an emacs style \sx or \Sx construct.
2602    //
2603    if(++m_position == m_end)
2604    {
2605       // Rewind to start of sequence:
2606       --m_position;
2607       while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_escape) --m_position;
2608       fail(regex_constants::error_escape, m_position - m_base);
2609       return false;
2610    }
2611    basic_char_set<charT, traits> char_set;
2612    if(negate)
2613       char_set.negate();
2614
2615    static const charT s_punct[5] = { 'p', 'u', 'n', 'c', 't', };
2616
2617    switch(*m_position)
2618    {
2619    case 's':
2620    case ' ':
2621       char_set.add_class(this->m_mask_space);
2622       break;
2623    case 'w':
2624       char_set.add_class(this->m_word_mask);
2625       break;
2626    case '_':
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       char_set.add_single(digraph<charT>(charT('<')));
2634       char_set.add_single(digraph<charT>(charT('>')));
2635       break;
2636    case '.':
2637       char_set.add_class(this->m_traits.lookup_classname(s_punct, s_punct+5));
2638       break;
2639    case '(':
2640       char_set.add_single(digraph<charT>(charT('(')));
2641       char_set.add_single(digraph<charT>(charT('[')));
2642       char_set.add_single(digraph<charT>(charT('{')));
2643       break;
2644    case ')':
2645       char_set.add_single(digraph<charT>(charT(')')));
2646       char_set.add_single(digraph<charT>(charT(']')));
2647       char_set.add_single(digraph<charT>(charT('}')));
2648       break;
2649    case '"':
2650       char_set.add_single(digraph<charT>(charT('"')));
2651       char_set.add_single(digraph<charT>(charT('\'')));
2652       char_set.add_single(digraph<charT>(charT('`')));
2653       break;
2654    case '\'':
2655       char_set.add_single(digraph<charT>(charT('\'')));
2656       char_set.add_single(digraph<charT>(charT(',')));
2657       char_set.add_single(digraph<charT>(charT('#')));
2658       break;
2659    case '<':
2660       char_set.add_single(digraph<charT>(charT(';')));
2661       break;
2662    case '>':
2663       char_set.add_single(digraph<charT>(charT('\n')));
2664       char_set.add_single(digraph<charT>(charT('\f')));
2665       break;
2666    default:
2667       fail(regex_constants::error_ctype, m_position - m_base);
2668       return false;
2669    }
2670    if(0 == this->append_set(char_set))
2671    {
2672       fail(regex_constants::error_ctype, m_position - m_base);
2673       return false;
2674    }
2675    ++m_position;
2676    return true;
2677 }
2678
2679 template <class charT, class traits>
2680 regex_constants::syntax_option_type basic_regex_parser<charT, traits>::parse_options()
2681 {
2682    // we have a (?imsx-imsx) group, convert it into a set of flags:
2683    regex_constants::syntax_option_type f = this->flags();
2684    bool breakout = false;
2685    do
2686    {
2687       switch(*m_position)
2688       {
2689       case 's':
2690          f |= regex_constants::mod_s;
2691          f &= ~regex_constants::no_mod_s;
2692          break;
2693       case 'm':
2694          f &= ~regex_constants::no_mod_m;
2695          break;
2696       case 'i':
2697          f |= regex_constants::icase;
2698          break;
2699       case 'x':
2700          f |= regex_constants::mod_x;
2701          break;
2702       default:
2703          breakout = true;
2704          continue;
2705       }
2706       if(++m_position == m_end)
2707       {
2708          // Rewind to start of (? sequence:
2709          --m_position;
2710          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2711          fail(regex_constants::error_paren, m_position - m_base);
2712          return false;
2713       }
2714    }
2715    while(!breakout);
2716
2717    breakout = false;
2718
2719    if(*m_position == static_cast<charT>('-'))
2720    {
2721       if(++m_position == m_end)
2722       {
2723          // Rewind to start of (? sequence:
2724          --m_position;
2725          while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2726          fail(regex_constants::error_paren, m_position - m_base);
2727          return false;
2728       }
2729       do
2730       {
2731          switch(*m_position)
2732          {
2733          case 's':
2734             f &= ~regex_constants::mod_s;
2735             f |= regex_constants::no_mod_s;
2736             break;
2737          case 'm':
2738             f |= regex_constants::no_mod_m;
2739             break;
2740          case 'i':
2741             f &= ~regex_constants::icase;
2742             break;
2743          case 'x':
2744             f &= ~regex_constants::mod_x;
2745             break;
2746          default:
2747             breakout = true;
2748             continue;
2749          }
2750          if(++m_position == m_end)
2751          {
2752             // Rewind to start of (? sequence:
2753             --m_position;
2754             while(this->m_traits.syntax_type(*m_position) != regex_constants::syntax_open_mark) --m_position;
2755             fail(regex_constants::error_paren, m_position - m_base);
2756             return false;
2757          }
2758       }
2759       while(!breakout);
2760    }
2761    return f;
2762 }
2763
2764 template <class charT, class traits>
2765 bool basic_regex_parser<charT, traits>::unwind_alts(std::ptrdiff_t last_paren_start)
2766 {
2767    //
2768    // If we didn't actually add any states after the last
2769    // alternative then that's an error:
2770    //
2771    if((this->m_alt_insert_point == static_cast<std::ptrdiff_t>(this->m_pdata->m_data.size()))
2772       && m_alt_jumps.size() && (m_alt_jumps.back() > last_paren_start)
2773       &&
2774       !(
2775          ((this->flags() & regbase::main_option_type) == regbase::perl_syntax_group)
2776            &&
2777          ((this->flags() & regbase::no_empty_expressions) == 0)
2778         )
2779       )
2780    {
2781       fail(regex_constants::error_empty, this->m_position - this->m_base, "Can't terminate a sub-expression with an alternation operator |.");
2782       return false;
2783    }
2784    //
2785    // Fix up our alternatives:
2786    //
2787    while(m_alt_jumps.size() && (m_alt_jumps.back() > last_paren_start))
2788    {
2789       //
2790       // fix up the jump to point to the end of the states
2791       // that we've just added:
2792       //
2793       std::ptrdiff_t jump_offset = m_alt_jumps.back();
2794       m_alt_jumps.pop_back();
2795       this->m_pdata->m_data.align();
2796       re_jump* jmp = static_cast<re_jump*>(this->getaddress(jump_offset));
2797       BOOST_ASSERT(jmp->type == syntax_element_jump);
2798       jmp->alt.i = this->m_pdata->m_data.size() - jump_offset;
2799    }
2800    return true;
2801 }
2802
2803 #ifdef BOOST_MSVC
2804 #pragma warning(pop)
2805 #endif
2806
2807 } // namespace re_detail
2808 } // namespace boost
2809
2810 #ifdef BOOST_MSVC
2811 #pragma warning(push)
2812 #pragma warning(disable: 4103)
2813 #endif
2814 #ifdef BOOST_HAS_ABI_HEADERS
2815 #  include BOOST_ABI_SUFFIX
2816 #endif
2817 #ifdef BOOST_MSVC
2818 #pragma warning(pop)
2819 #endif
2820
2821 #endif