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