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