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