boost/boost/regex/v4/basic_regex_parser.hpp

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