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