boost/boost/regex/v4/regex_compile.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2002
   4  * Dr 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         regex_compile.hpp
  15   *   VERSION      see <boost/version.hpp>
  16   *   DESCRIPTION: Declares reg_expression<> member functions.  This is
  17   *                an internal header file, do not include directly.
  18   */
  19
  20 #ifndef BOOST_REGEX_COMPILE_HPP
  21 #define BOOST_REGEX_COMPILE_HPP
  22
  23 namespace boost{
  24 #ifdef BOOST_HAS_ABI_HEADERS
  25 #  include BOOST_ABI_PREFIX
  26 #endif
  27 #ifdef __BORLANDC__
  28 #pragma option push -w-8004
  29 #endif
  30
  31 namespace re_detail{
  32
  33
  34 template <class traits>
  35 struct kmp_translator
  36 {
  37    typedef typename traits::char_type char_type;
  38    bool icase;
  39    const traits* pt;
  40    kmp_translator(bool c, traits* p) : icase(c), pt(p) {}
  41    char_type operator()(char_type c)
  42    {
  43       return pt->translate(c, icase);
  44    }
  45 };
  46
  47
  48 template <class charT, class traits_type, class Allocator>
  49 bool BOOST_REGEX_CALL re_maybe_set_member(charT c,
  50                                  const re_set_long* set_,
  51                                  const reg_expression<charT, traits_type, Allocator>& e)
  52 {
  53    const charT* p = reinterpret_cast<const charT*>(set_+1);
  54    bool icase = e.flags() & regex_constants::icase;
  55    charT col = e.get_traits().translate(c, icase);
  56    for(unsigned int i = 0; i < set_->csingles; ++i)
  57    {
  58       if(col == *p)
  59          return set_->isnot ? false : true;
  60
  61       while(*p)++p;
  62       ++p;     // skip null
  63    }
  64    return set_->isnot ? true : false;
  65 }
  66
  67 } // namespace re_detail
  68
  69 template <class traits>
  70 struct is_big_char
  71 {
  72    typedef typename traits::uchar_type traits_uchar_type;
  73    typedef typename traits::size_type traits_size_type;
  74 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1200)
  75    static bool test(char)
  76    { return false; }
  77    static bool test(unsigned char)
  78    { return false; }
  79    static bool test(signed char)
  80    { return false; }
  81 #endif
  82    template <class charT> static bool test(charT c)
  83    { return (traits_size_type)(traits_uchar_type)c >= 256; }
  84 };
  85
  86 template <class charT, class traits, class Allocator>
  87 inline bool BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::can_start(charT c, const unsigned char* _map, unsigned char mask, const re_detail::_wide_type&)
  88 {
  89    if(is_big_char<traits>::test(c))
  90       return true;
  91    return BOOST_REGEX_MAKE_BOOL(_map[(traits_uchar_type)c] & mask);
  92 }
  93
  94 template <class charT, class traits, class Allocator>
  95 inline bool BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::can_start(charT c, const unsigned char* _map, unsigned char mask, const re_detail::_narrow_type&)
  96 {
  97    return BOOST_REGEX_MAKE_BOOL(_map[(traits_uchar_type)c] & mask);
  98 }
  99
 100 template <class charT, class traits, class Allocator>
 101 reg_expression<charT, traits, Allocator>::reg_expression(const Allocator& a)
 102     : regbase(), data(a), pkmp(0), error_code_(REG_EMPTY), _expression(0)
 103 {
 104 }
 105
 106 template <class charT, class traits, class Allocator>
 107 reg_expression<charT, traits, Allocator>::reg_expression(const charT* p, flag_type f, const Allocator& a)
 108     : data(a), pkmp(0), error_code_(REG_EMPTY), _expression(0)
 109 {
 110    set_expression(p, f | regex_constants::use_except);
 111 }
 112
 113 template <class charT, class traits, class Allocator>
 114 reg_expression<charT, traits, Allocator>::reg_expression(const charT* p1, const charT* p2, flag_type f, const Allocator& a)
 115     : data(a), pkmp(0), error_code_(REG_EMPTY), _expression(0)
 116 {
 117     set_expression(p1, p2, f | regex_constants::use_except);
 118 }
 119
 120 template <class charT, class traits, class Allocator>
 121 reg_expression<charT, traits, Allocator>::reg_expression(const charT* p, size_type len, flag_type f, const Allocator& a)
 122     : data(a), pkmp(0), error_code_(REG_EMPTY), _expression(0)
 123 {
 124     set_expression(p, p + len, f | regex_constants::use_except);
 125 }
 126
 127 template <class charT, class traits, class Allocator>
 128 reg_expression<charT, traits, Allocator>::reg_expression(const reg_expression<charT, traits, Allocator>& e)
 129    : regbase(e), data(e.allocator()), pkmp(0), error_code_(REG_EMPTY), _expression(0)
 130 {
 131    //
 132    // we do a deep copy only if e is a valid expression, otherwise fail.
 133    //
 134    if(e.error_code() == 0)
 135    {
 136       const charT* pe = e.expression();
 137       set_expression(pe, pe + e._expression_len, e.flags() | regex_constants::use_except);
 138    }
 139    else
 140    {
 141       _flags = e.flags() & ~(regex_constants::use_except);
 142       fail(e.error_code());
 143    }
 144 }
 145
 146 template <class charT, class traits, class Allocator>
 147 reg_expression<charT, traits, Allocator>::~reg_expression()
 148 {
 149    if(pkmp)
 150       re_detail::kmp_free(pkmp, data.allocator());
 151 }
 152
 153 template <class charT, class traits, class Allocator>
 154 reg_expression<charT, traits, Allocator>& BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::operator=(const reg_expression<charT, traits, Allocator>& e)
 155 {
 156    //
 157    // we do a deep copy only if e is a valid expression, otherwise fail.
 158    //
 159    if(this == &e) return *this;
 160    _flags = use_except;
 161    fail(e.error_code());
 162    if(error_code() == 0)
 163       set_expression(e._expression, e._expression + e._expression_len, e.flags() | regex_constants::use_except);
 164    return *this;
 165 }
 166
 167 template <class charT, class traits, class Allocator>
 168 int BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compare(const reg_expression<charT, traits, Allocator>& e)const
 169 {
 170    if(_flags != e.flags())
 171       return _flags - e.flags();
 172    return str().compare(e.str());
 173 }
 174
 175 template <class charT, class traits, class Allocator>
 176 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::swap(reg_expression& that)throw()
 177 {
 178    traits_inst.swap(that.traits_inst);
 179    data.swap(that.data);
 180    static_cast<regbase&>(*this).swap(that);
 181
 182    std::swap(_restart_type, that._restart_type);
 183    std::swap(marks, that.marks);
 184    std::swap(repeats, that.repeats);
 185    std::swap(startmap, that.startmap);
 186    std::swap(_expression_len, that._expression_len);
 187    std::swap(_leading_len, that._leading_len);
 188    std::swap(_leading_string, that._leading_string);
 189    std::swap(_leading_string_len, that._leading_string_len);
 190    std::swap(pkmp, that.pkmp);
 191    std::swap(error_code_, that.error_code_);
 192    std::swap(_expression, that._expression);
 193 }
 194
 195 template <class charT, class traits, class Allocator>
 196 Allocator BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::allocator()const
 197 {
 198     return data.allocator();
 199 }
 200
 201 template <class charT, class traits, class Allocator>
 202 Allocator BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::get_allocator()const
 203 {
 204     return data.allocator();
 205 }
 206
 207 template <class charT, class traits, class Allocator>
 208 unsigned int BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::parse_inner_set(const charT*& arg_first, const charT* arg_last)
 209 {
 210    //
 211    // we have an inner [...] construct
 212    //
 213    jm_assert(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*arg_first) == traits_type::syntax_open_set);
 214    const charT* base = arg_first;
 215    while( (arg_first != arg_last)
 216       && (traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*arg_first) != traits_type::syntax_close_set) )
 217          ++arg_first;
 218    if(arg_first == arg_last)
 219       return 0;
 220    ++arg_first;
 221    if((arg_first-base) < 5)
 222       return 0;
 223    if(*(base+1) != *(arg_first-2))
 224       return 0;
 225    unsigned int result = traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*(base+1));
 226    if((result == traits_type::syntax_colon) && ((arg_first-base) == 5))
 227    {
 228       unsigned type = traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*(base+2));
 229       if((type == traits_type::syntax_left_word) || (type == traits_type::syntax_right_word))
 230          return type;
 231    }
 232    return ((result == traits_type::syntax_colon) || (result == traits_type::syntax_dot) || (result == traits_type::syntax_equal)) ? result : 0;
 233 }
 234
 235
 236 template <class charT, class traits, class Allocator>
 237 bool BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::skip_space(const charT*& arg_first, const charT* arg_last)
 238 {
 239    //
 240    // returns true if we get to arg_last:
 241    //
 242    while((arg_first != arg_last) && (traits_inst.is_class(*arg_first, traits_type::char_class_space) == true))
 243    {
 244       ++arg_first;
 245    }
 246    return arg_first == arg_last;
 247 }
 248
 249 template <class charT, class traits, class Allocator>
 250 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::parse_range(const charT*& ptr, const charT* arg_end, unsigned& min, unsigned& max)
 251 {
 252    //
 253    // we have {x} or {x,} or {x,y} NB no spaces inside braces
 254    // anything else is illegal
 255    // On input ptr points to "{"
 256    //
 257    ++ptr;
 258    if(skip_space(ptr, arg_end))
 259    {
 260       fail(REG_EBRACE);
 261       return;
 262    }
 263    if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) != traits_type::syntax_digit)
 264    {
 265       fail(REG_BADBR);
 266       return;
 267    }
 268    min = traits_inst.toi(ptr, arg_end, 10);
 269    if(skip_space(ptr, arg_end))
 270    {
 271       fail(REG_EBRACE);
 272       return;
 273    }
 274    if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) == traits_type::syntax_comma)
 275    {
 276       //we have a second interval:
 277       ++ptr;
 278       if(skip_space(ptr, arg_end))
 279       {
 280          fail(REG_EBRACE);
 281          return;
 282       }
 283       if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) == traits_type::syntax_digit)
 284          max = traits_inst.toi(ptr, arg_end, 10);
 285       else
 286          max = (unsigned)-1;
 287    }
 288    else
 289       max = min;
 290
 291    // validate input:
 292    if(skip_space(ptr, arg_end))
 293    {
 294       fail(REG_EBRACE);
 295       return;
 296    }
 297    if(max < min)
 298    {
 299       fail(REG_ERANGE);
 300       return;
 301    }
 302    if(_flags & bk_braces)
 303    {
 304       if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) != traits_type::syntax_slash)
 305       {
 306          fail(REG_BADBR);
 307          return;
 308       }
 309       else
 310       {
 311          // back\ is OK now check the }
 312          ++ptr;
 313          if((ptr == arg_end) || (traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) != traits_type::syntax_close_brace))
 314          {
 315             fail(REG_BADBR);
 316             return;
 317          }
 318       }
 319    }
 320    else if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) != traits_type::syntax_close_brace)
 321    {
 322       fail(REG_BADBR);
 323       return;
 324    }
 325 }
 326
 327 template <class charT, class traits, class Allocator>
 328 charT BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::parse_escape(const charT*& arg_first, const charT* arg_last)
 329 {
 330    charT c(*arg_first);
 331    traits_size_type c_unsigned = (traits_size_type)(traits_uchar_type)*arg_first;
 332    // this is only used for the switch(), but cannot be folded in
 333    // due to a bug in Comeau 4.2.44beta3
 334    traits_size_type syntax = traits_inst.syntax_type(c_unsigned);
 335    switch(syntax)
 336    {
 337    case traits_type::syntax_a:
 338       c = '\a';
 339       ++arg_first;
 340       break;
 341    case traits_type::syntax_f:
 342       c = '\f';
 343       ++arg_first;
 344       break;
 345    case traits_type::syntax_n:
 346       c = '\n';
 347       ++arg_first;
 348       break;
 349    case traits_type::syntax_r:
 350       c = '\r';
 351       ++arg_first;
 352       break;
 353    case traits_type::syntax_t:
 354       c = '\t';
 355       ++arg_first;
 356       break;
 357    case traits_type::syntax_v:
 358       c = '\v';
 359       ++arg_first;
 360       break;
 361    case traits_type::syntax_x:
 362       ++arg_first;
 363       if(arg_first == arg_last)
 364       {
 365          fail(REG_EESCAPE);
 366          break;
 367       }
 368       // maybe have \x{ddd}
 369       if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)(*arg_first)) == traits_type::syntax_open_brace)
 370       {
 371          ++arg_first;
 372          if(arg_first == arg_last)
 373          {
 374             fail(REG_EESCAPE);
 375             break;
 376          }
 377          if(traits_inst.is_class(*arg_first, traits_type::char_class_xdigit) == false)
 378          {
 379             fail(REG_BADBR);
 380             break;
 381          }
 382          c = (charT)traits_inst.toi(arg_first, arg_last, -16);
 383          if((arg_first == arg_last) || (traits_inst.syntax_type((traits_size_type)(traits_uchar_type)(*arg_first)) != traits_type::syntax_close_brace))
 384          {
 385             fail(REG_BADBR);
 386          }
 387          ++arg_first;
 388          break;
 389       }
 390       else
 391       {
 392          if(traits_inst.is_class(*arg_first, traits_type::char_class_xdigit) == false)
 393          {
 394             fail(REG_BADBR);
 395             break;
 396          }
 397          c = (charT)traits_inst.toi(arg_first, arg_last, -16);
 398       }
 399       break;
 400    case traits_type::syntax_c:
 401       ++arg_first;
 402       if(arg_first == arg_last)
 403       {
 404          fail(REG_EESCAPE);
 405          break;
 406       }
 407       if(((traits_uchar_type)(*arg_first) < (traits_uchar_type)'@')
 408             || ((traits_uchar_type)(*arg_first) > (traits_uchar_type)127) )
 409       {
 410          fail(REG_EESCAPE);
 411          return (charT)0;
 412       }
 413       c = (charT)((traits_uchar_type)(*arg_first) - (traits_uchar_type)'@');
 414       ++arg_first;
 415       break;
 416    case traits_type::syntax_e:
 417       c = (charT)27;
 418       ++arg_first;
 419       break;
 420    case traits_type::syntax_digit:
 421       c = (charT)traits_inst.toi(arg_first, arg_last, -8);
 422       break;
 423    default:
 424       //c = *arg_first;
 425       ++arg_first;
 426    }
 427    return c;
 428 }
 429
 430 template <class charT, class traits, class Allocator>
 431 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compile_maps()
 432 {
 433    re_detail::re_syntax_base* record = static_cast<re_detail::re_syntax_base*>(data.data());
 434    // always compile the first _map:
 435    std::memset(startmap, 0, 256);
 436    record->can_be_null = 0;
 437    compile_map(record, startmap, 0, re_detail::mask_all);
 438
 439    while(record->type != re_detail::syntax_element_match)
 440    {
 441       if((record->type == re_detail::syntax_element_alt) || (record->type == re_detail::syntax_element_rep))
 442       {
 443          std::memset(&(static_cast<re_detail::re_jump*>(record)->_map), 0, 256);
 444          record->can_be_null = 0;
 445          compile_map(record->next.p, static_cast<re_detail::re_jump*>(record)->_map, &(record->can_be_null), re_detail::mask_take, static_cast<re_detail::re_jump*>(record)->alt.p);
 446          compile_map(static_cast<re_detail::re_jump*>(record)->alt.p, static_cast<re_detail::re_jump*>(record)->_map, &(record->can_be_null), re_detail::mask_skip);
 447          if(record->type == re_detail::syntax_element_rep)
 448          {
 449             re_detail::re_repeat* rep = static_cast<re_detail::re_repeat*>(record);
 450             // set whether this is a singleton repeat or not:
 451             if(rep->next.p->next.p->next.p == rep->alt.p)
 452             {
 453                switch(rep->next.p->type)
 454                {
 455                case re_detail::syntax_element_wild:
 456                   rep->type = re_detail::syntax_element_dot_rep;
 457                   break;
 458                case re_detail::syntax_element_literal:
 459                   rep->type = re_detail::syntax_element_char_rep;
 460                   break;
 461                case re_detail::syntax_element_set:
 462                   rep->type = re_detail::syntax_element_short_set_rep;
 463                   break;
 464                case re_detail::syntax_element_long_set:
 465                   if(static_cast<re_detail::re_set_long*>(rep->next.p)->singleton)
 466                      rep->type = re_detail::syntax_element_long_set_rep;
 467                   break;
 468                default:
 469                   break;
 470                }
 471             }
 472          }
 473       }
 474       else
 475       {
 476          record->can_be_null = 0;
 477          compile_map(record, 0, &(record->can_be_null), re_detail::mask_all);
 478       }
 479       record = record->next.p;
 480    }
 481    record->can_be_null = re_detail::mask_all;
 482 }
 483
 484 template <class charT, class traits, class Allocator>
 485 bool BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::probe_start(
 486                         re_detail::re_syntax_base* node, charT cc, re_detail::re_syntax_base* terminal) const
 487 {
 488    unsigned int c;
 489
 490    switch(node->type)
 491    {
 492    case re_detail::syntax_element_startmark:
 493       if(static_cast<const re_detail::re_brace*>(node)->index == -1)
 494       {
 495          return probe_start(node->next.p->next.p, cc, terminal)
 496             && probe_start(static_cast<const re_detail::re_jump*>(node->next.p)->alt.p, cc, terminal);
 497       }
 498       else if(static_cast<const re_detail::re_brace*>(node)->index == -3)
 499       {
 500          return probe_start(node->next.p->next.p, cc, terminal);
 501       }
 502       // doesn't tell us anything about the next character, so:
 503       return probe_start(node->next.p, cc, terminal);
 504    case re_detail::syntax_element_endmark:
 505       if(static_cast<const re_detail::re_brace*>(node)->index == -3)
 506       {
 507          return true;
 508       }
 509       // fall through:
 510    case re_detail::syntax_element_start_line:
 511    case re_detail::syntax_element_word_boundary:
 512    case re_detail::syntax_element_buffer_start:
 513    case re_detail::syntax_element_restart_continue:
 514       // doesn't tell us anything about the next character, so:
 515       return probe_start(node->next.p, cc, terminal);
 516    case re_detail::syntax_element_literal:
 517       // only the first character of the literal can match:
 518       // note these have already been translated:
 519       if(*reinterpret_cast<charT*>(static_cast<re_detail::re_literal*>(node)+1) == traits_inst.translate(cc, (_flags & regex_constants::icase)))
 520          return true;
 521       return false;
 522    case re_detail::syntax_element_end_line:
 523       // next character (if there is one!) must be a newline:
 524       if(traits_inst.is_separator(traits_inst.translate(cc, (_flags & regex_constants::icase))))
 525          return true;
 526       return false;
 527    case re_detail::syntax_element_wild:
 528       return true;
 529    case re_detail::syntax_element_match:
 530       return true;
 531    case re_detail::syntax_element_within_word:
 532    case re_detail::syntax_element_word_start:
 533       return traits_inst.is_class(traits_inst.translate(cc, (_flags & regex_constants::icase)), traits_type::char_class_word);
 534    case re_detail::syntax_element_word_end:
 535       // what follows must not be a word character,
 536       return traits_inst.is_class(traits_inst.translate(cc, (_flags & regex_constants::icase)), traits_type::char_class_word) ? false : true;
 537    case re_detail::syntax_element_buffer_end:
 538       // we can be null, nothing must follow,
 539       // NB we assume that this is followed by
 540       // re_detail::syntax_element_match, if its not then we can
 541       // never match anything anyway!!
 542       return false;
 543    case re_detail::syntax_element_soft_buffer_end:
 544       // we can be null, only newlines must follow,
 545       // NB we assume that this is followed by
 546       // re_detail::syntax_element_match, if its not then we can
 547       // never match anything anyway!!
 548       return traits_inst.is_separator(traits_inst.translate(cc, (_flags & regex_constants::icase)));
 549    case re_detail::syntax_element_backref:
 550       // there's no easy way to determine this
 551       // which is not to say it can't be done!
 552       // for now:
 553       return true;
 554    case re_detail::syntax_element_long_set:
 555       // we can not be null,
 556       // we need to add already translated values in the set
 557       // to values in the _map
 558       return re_detail::re_maybe_set_member(cc, static_cast<const re_detail::re_set_long*>(node), *this) || (re_detail::re_is_set_member(static_cast<const charT*>(&cc), static_cast<const charT*>(&cc+1), static_cast<re_detail::re_set_long*>(node), *this) != &cc);
 559    case re_detail::syntax_element_set:
 560       // set all the elements that are set in corresponding set:
 561       c = (traits_size_type)(traits_uchar_type)traits_inst.translate(cc, (_flags & regex_constants::icase));
 562       return static_cast<re_detail::re_set*>(node)->_map[c] != 0;
 563    case re_detail::syntax_element_jump:
 564       if(static_cast<re_detail::re_jump*>(node)->alt.p < node)
 565       {
 566          // backwards jump,
 567          // caused only by end of repeat section, we'll treat this
 568          // the same as a match, because the sub-expression has matched.
 569          if(node->next.p == terminal)
 570             return true; // null repeat - we can always take this
 571          else
 572          {
 573             //
 574             // take the jump, add in fix for the fact that if the
 575             // repeat that we're jumping to has non-zero minimum count
 576             // then we need to add in the possiblity that we could still
 577             // skip that repeat.
 578             re_detail::re_syntax_base* next = static_cast<re_detail::re_jump*>(node)->alt.p;
 579             bool b = probe_start(next, cc, terminal);
 580             if((next->type == re_detail::syntax_element_rep) && (static_cast<re_detail::re_repeat*>(next)->min != 0))
 581             {
 582                b = b || probe_start(static_cast<re_detail::re_jump*>(next)->alt.p, cc, terminal);
 583             }
 584             return b;
 585          }
 586       }
 587       else
 588          // take the jump and compile:
 589          return probe_start(static_cast<re_detail::re_jump*>(node)->alt.p, cc, terminal);
 590    case re_detail::syntax_element_alt:
 591       // we need to take the OR of the two alternatives:
 592       return probe_start(static_cast<re_detail::re_jump*>(node)->alt.p, cc, terminal) || probe_start(node->next.p, cc, terminal);
 593    case re_detail::syntax_element_rep:
 594    case re_detail::syntax_element_char_rep:
 595    case re_detail::syntax_element_dot_rep:
 596    case re_detail::syntax_element_long_set_rep:
 597    case re_detail::syntax_element_short_set_rep:
 598       // we need to take the OR of the two alternatives
 599       if(static_cast<re_detail::re_repeat*>(node)->min == 0)
 600          return probe_start(node->next.p, cc, static_cast<re_detail::re_jump*>(node)->alt.p) || probe_start(static_cast<re_detail::re_jump*>(node)->alt.p, cc, terminal);
 601       else
 602          return probe_start(node->next.p, cc, static_cast<re_detail::re_jump*>(node)->alt.p);
 603    case re_detail::syntax_element_combining:
 604       return !traits_inst.is_combining(traits_inst.translate(cc, (_flags & regex_constants::icase)));
 605    }
 606    return false;
 607 }
 608
 609 template <class charT, class traits, class Allocator>
 610 bool BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::probe_start_null(re_detail::re_syntax_base* node, re_detail::re_syntax_base* terminal)const
 611 {
 612    switch(node->type)
 613    {
 614    case re_detail::syntax_element_endmark:
 615       if(static_cast<const re_detail::re_brace*>(node)->index == -3)
 616       {
 617          return true;
 618       }
 619       // fall through:
 620    case re_detail::syntax_element_startmark:
 621    case re_detail::syntax_element_start_line:
 622    case re_detail::syntax_element_word_boundary:
 623    case re_detail::syntax_element_buffer_start:
 624    case re_detail::syntax_element_restart_continue:
 625    case re_detail::syntax_element_end_line:
 626    case re_detail::syntax_element_word_end:
 627       // doesn't tell us anything about the next character, so:
 628       return probe_start_null(node->next.p, terminal);
 629    case re_detail::syntax_element_match:
 630    case re_detail::syntax_element_buffer_end:
 631    case re_detail::syntax_element_soft_buffer_end:
 632    case re_detail::syntax_element_backref:
 633       return true;
 634    case re_detail::syntax_element_jump:
 635       if(static_cast<re_detail::re_jump*>(node)->alt.p < node)
 636       {
 637          // backwards jump,
 638          // caused only by end of repeat section, we'll treat this
 639          // the same as a match, because the sub-expression has matched.
 640          // this is only caused by NULL repeats as in "(a*)*" or "(\<)*"
 641          // these are really nonsensence and make the matching code much
 642          // harder, it would be nice to get rid of them altogether.
 643          if(node->next.p == terminal)
 644             return true;
 645          else
 646             return probe_start_null(static_cast<re_detail::re_jump*>(node)->alt.p, terminal);
 647       }
 648       else
 649          // take the jump and compile:
 650          return probe_start_null(static_cast<re_detail::re_jump*>(node)->alt.p, terminal);
 651    case re_detail::syntax_element_alt:
 652       // we need to take the OR of the two alternatives:
 653       return probe_start_null(static_cast<re_detail::re_jump*>(node)->alt.p, terminal) || probe_start_null(node->next.p, terminal);
 654    case re_detail::syntax_element_rep:
 655       // only need to consider skipping the repeat:
 656       return probe_start_null(static_cast<re_detail::re_jump*>(node)->alt.p, terminal);
 657    default:
 658       break;
 659    }
 660    return false;
 661 }
 662
 663 template <class charT, class traits, class Allocator>
 664 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compile_map(
 665                         re_detail::re_syntax_base* node, unsigned char* _map,
 666                         unsigned int* pnull, unsigned char mask, re_detail::re_syntax_base* terminal)const
 667 {
 668    if(_map)
 669    {
 670       for(unsigned int i = 0; i < 256; ++i)
 671       {
 672          if(probe_start(node, (charT)i, terminal))
 673             _map[i] |= mask;
 674       }
 675    }
 676    if(pnull && probe_start_null(node, terminal))
 677       *pnull |= mask;
 678 }
 679
 680 template <class charT, class traits, class Allocator>
 681 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::move_offsets(re_detail::re_syntax_base* j, unsigned arg_size)
 682 {
 683 # ifdef BOOST_MSVC
 684 #  pragma warning(push)
 685 #  pragma warning(disable: 4127)
 686 #endif
 687    // move all offsets starting with j->link forward by arg_size
 688    // called after an insert:
 689    j = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<char*>(data.data()) + j->next.i);
 690    while(true)
 691    {
 692       switch(j->type)
 693       {
 694       case re_detail::syntax_element_rep:
 695          static_cast<re_detail::re_jump*>(j)->alt.i += arg_size;
 696          j->next.i += arg_size;
 697          break;
 698       case re_detail::syntax_element_jump:
 699       case re_detail::syntax_element_alt:
 700          static_cast<re_detail::re_jump*>(j)->alt.i += arg_size;
 701          j->next.i += arg_size;
 702          break;
 703       default:
 704          j->next.i += arg_size;
 705          break;
 706       }
 707       if(j->next.i == arg_size)
 708          break;
 709       j = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<char*>(data.data()) + j->next.i);
 710    }
 711 # ifdef BOOST_MSVC
 712 #  pragma warning(pop)
 713 #endif
 714 }
 715
 716 template <class charT, class traits, class Allocator>
 717 re_detail::re_syntax_base* BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compile_set_simple(re_detail::re_syntax_base* dat, unsigned long cls, bool isnot)
 718 {
 719    typedef typename re_detail::is_byte<charT>::width_type width_type;
 720    re_detail::jstack<traits_string_type, Allocator> singles(64, data.allocator());
 721    re_detail::jstack<traits_string_type, Allocator> ranges(64, data.allocator());
 722    re_detail::jstack<boost::uint_fast32_t, Allocator> classes(64, data.allocator());
 723    re_detail::jstack<traits_string_type, Allocator> equivalents(64, data.allocator());
 724    classes.push(cls);
 725    if(dat)
 726    {
 727       data.align();
 728       dat->next.i = data.size();
 729    }
 730    return compile_set_aux(singles, ranges, classes, equivalents, isnot, width_type());
 731 }
 732
 733 template <class charT, class traits, class Allocator>
 734 re_detail::re_syntax_base* BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compile_set(const charT*& arg_first, const charT* arg_last)
 735 {
 736    re_detail::jstack<traits_string_type, Allocator> singles(64, data.allocator());
 737    re_detail::jstack<traits_string_type, Allocator> ranges(64, data.allocator());
 738    re_detail::jstack<boost::uint_fast32_t, Allocator> classes(64, data.allocator());
 739    re_detail::jstack<traits_string_type, Allocator> equivalents(64, data.allocator());
 740    bool has_digraphs = false;
 741    jm_assert(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*arg_first) == traits_type::syntax_open_set);
 742    ++arg_first;
 743    bool started = false;
 744    bool done = false;
 745    bool isnot = false;
 746
 747    enum last_type
 748    {
 749       last_single,
 750       last_none,
 751       last_dash
 752    };
 753
 754    unsigned l = last_none;
 755    traits_string_type s;
 756
 757    while((arg_first != arg_last) && !done)
 758    {
 759       traits_size_type c = (traits_size_type)(traits_uchar_type)*arg_first;
 760       // this is only used for the switch(), but cannot be folded in
 761       // due to a bug in Comeau 4.2.44beta3
 762       traits_size_type syntax = traits_inst.syntax_type(c);
 763       switch(syntax)
 764       {
 765       case traits_type::syntax_caret:
 766          if(!started && !isnot)
 767          {
 768             isnot = true;
 769          }
 770          else
 771          {
 772             s = (charT)c;
 773             goto char_set_literal;
 774          }
 775          break;
 776       case traits_type::syntax_open_set:
 777       {
 778          if((_flags & char_classes) == 0)
 779          {
 780             s = (charT)c;
 781             goto char_set_literal;
 782          }
 783          // check to see if we really have a class:
 784          const charT* base = arg_first;
 785          // this is only used for the switch(), but cannot be folded in
 786          // due to a bug in Comeau 4.2.44beta3
 787     unsigned int inner_set = parse_inner_set(arg_first, arg_last);
 788          switch(inner_set)
 789          {
 790          case traits_type::syntax_colon:
 791             {
 792                if(l == last_dash)
 793                {
 794                   fail(REG_ERANGE);
 795                   return 0;
 796                }
 797                boost::uint_fast32_t id = traits_inst.lookup_classname(base+2, arg_first-2);
 798                if(_flags & regex_constants::icase)
 799                {
 800                   if((id == traits_type::char_class_upper) || (id == traits_type::char_class_lower))
 801                   {
 802                      id = traits_type::char_class_alpha;
 803                   }
 804                }
 805                if(id == 0)
 806                {
 807                   fail(REG_ECTYPE);
 808                   return 0;
 809                }
 810                classes.push(id);
 811                started = true;
 812                l = last_none;
 813             }
 814             break;
 815          case traits_type::syntax_dot:
 816             //
 817             // we have a collating element [.collating-name.]
 818             //
 819             if(traits_inst.lookup_collatename(s, base+2, arg_first-2))
 820             {
 821                --arg_first;
 822                if(s.size() > 1)
 823                   has_digraphs = true;
 824                if(s.size())goto char_set_literal;
 825             }
 826             fail(REG_ECOLLATE);
 827             return 0;
 828          case traits_type::syntax_equal:
 829             //
 830             // we have an equivalence class [=collating-name=]
 831             //
 832             if(traits_inst.lookup_collatename(s, base+2, arg_first-2))
 833             {
 834                std::size_t len = s.size();
 835                if(len)
 836                {
 837                   unsigned i = 0;
 838                   while(i < len)
 839                   {
 840                      s[i] = traits_inst.translate(s[i], (_flags & regex_constants::icase));
 841                      ++i;
 842                   }
 843                   traits_string_type s2;
 844                   traits_inst.transform_primary(s2, s);
 845                   equivalents.push(s2);
 846                   started = true;
 847                   l = last_none;
 848                   break;
 849                }
 850             }
 851             fail(REG_ECOLLATE);
 852             return 0;
 853          case traits_type::syntax_left_word:
 854             if((started == false) && (traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*arg_first) == traits_type::syntax_close_set))
 855             {
 856                ++arg_first;
 857                return add_simple(0, re_detail::syntax_element_word_start);
 858             }
 859             fail(REG_EBRACK);
 860             return 0;
 861          case traits_type::syntax_right_word:
 862             if((started == false) && (traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*arg_first) == traits_type::syntax_close_set))
 863             {
 864                ++arg_first;
 865                return add_simple(0, re_detail::syntax_element_word_end);
 866             }
 867             fail(REG_EBRACK);
 868             return 0;
 869          default:
 870             if(started == false)
 871             {
 872                unsigned int t = traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*(base+1));
 873                if((t != traits_type::syntax_colon) && (t != traits_type::syntax_dot) && (t != traits_type::syntax_equal))
 874                {
 875                   arg_first = base;
 876                   s = (charT)c;
 877                   goto char_set_literal;
 878                }
 879             }
 880             fail(REG_EBRACK);
 881             return 0;
 882          }
 883          if(arg_first == arg_last)
 884          {
 885             fail(REG_EBRACK);
 886             return 0;
 887          }
 888          continue;
 889       }
 890       case traits_type::syntax_close_set:
 891          if(started == false)
 892          {
 893             s = (charT)c;
 894             goto char_set_literal;
 895          }
 896          done = true;
 897          break;
 898       case traits_type::syntax_dash:
 899          if(!started)
 900          {
 901             s = (charT)c;
 902             goto char_set_literal;
 903          }
 904          ++arg_first;
 905          if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*arg_first) == traits_type::syntax_close_set)
 906          {
 907             --arg_first;
 908             s = (charT)c;
 909             goto char_set_literal;
 910          }
 911          if((singles.empty() == true) || (l != last_single))
 912          {
 913             fail(REG_ERANGE);
 914             return 0;
 915          }
 916          ranges.push(singles.peek());
 917          if(singles.peek().size() <= 1)  // leave digraphs and ligatures in place
 918             singles.pop();
 919          l = last_dash;
 920          continue;
 921       case traits_type::syntax_slash:
 922          if(_flags & regex_constants::escape_in_lists)
 923          {
 924             ++arg_first;
 925             if(arg_first == arg_last)
 926                continue;
 927             /*traits_size_type*/ c = (traits_size_type)(traits_uchar_type)*arg_first;
 928             // this is only used for the switch(), but cannot be folded in
 929             // due to a bug in Comeau 4.2.44beta3
 930             traits_size_type syntax4 = traits_inst.syntax_type(c);
 931             switch(syntax4)
 932             {
 933             case traits_type::syntax_w:
 934                if(l == last_dash)
 935                {
 936                   fail(REG_ERANGE);
 937                   return 0;
 938                }
 939                classes.push(traits_type::char_class_word);
 940                started = true;
 941                l = last_none;
 942                ++arg_first;
 943                continue;
 944             case traits_type::syntax_d:
 945                if(l == last_dash)
 946                {
 947                   fail(REG_ERANGE);
 948                   return 0;
 949                }
 950                classes.push(traits_type::char_class_digit);
 951                started = true;
 952                l = last_none;
 953                ++arg_first;
 954                continue;
 955             case traits_type::syntax_s:
 956                if(l == last_dash)
 957                {
 958                   fail(REG_ERANGE);
 959                   return 0;
 960                }
 961                classes.push(traits_type::char_class_space);
 962                started = true;
 963                l = last_none;
 964                ++arg_first;
 965                continue;
 966             case traits_type::syntax_l:
 967                if(l == last_dash)
 968                {
 969                   fail(REG_ERANGE);
 970                   return 0;
 971                }
 972                classes.push(traits_type::char_class_lower);
 973                started = true;
 974                l = last_none;
 975                ++arg_first;
 976                continue;
 977             case traits_type::syntax_u:
 978                if(l == last_dash)
 979                {
 980                   fail(REG_ERANGE);
 981                   return 0;
 982                }
 983                classes.push(traits_type::char_class_upper);
 984                started = true;
 985                l = last_none;
 986                ++arg_first;
 987                continue;
 988             case traits_type::syntax_W:
 989             case traits_type::syntax_D:
 990             case traits_type::syntax_S:
 991             case traits_type::syntax_U:
 992             case traits_type::syntax_L:
 993                fail(REG_EESCAPE);
 994                return 0;
 995             default:
 996                c = parse_escape(arg_first, arg_last);
 997                --arg_first;
 998                s = (charT)c;
 999                goto char_set_literal;
1000             }
1001          }
1002          else
1003          {
1004             s = (charT)c;
1005             goto char_set_literal;
1006          }
1007       default:
1008          s = (charT)c;
1009          char_set_literal:
1010          unsigned i = 0;
1011          // get string length to stop us going past the end of string (DWA)
1012          std::size_t len = s.size();
1013          while(i < len)
1014          {
1015             s[i] = traits_inst.translate(s[i], (_flags & regex_constants::icase));
1016             ++i;
1017          }
1018          started = true;
1019          if(l == last_dash)
1020          {
1021             ranges.push(s);
1022             l = last_none;
1023             if(s.size() > 1)   // add ligatures to singles list as well
1024                singles.push(s);
1025          }
1026          else
1027          {
1028             singles.push(s);
1029             l = last_single;
1030          }
1031       }
1032       ++arg_first;
1033    }
1034    if(!done)
1035       return 0;
1036
1037    typedef typename re_detail::is_byte<charT>::width_type width_type;
1038
1039    re_detail::re_syntax_base* result;
1040    if(has_digraphs)
1041       result = compile_set_aux(singles, ranges, classes, equivalents, isnot, re_detail::_wide_type());
1042    else
1043       result = compile_set_aux(singles, ranges, classes, equivalents, isnot, width_type());
1044    #ifdef __BORLANDC__
1045    // delayed throw:
1046    if((result == 0) && (_flags & regex_constants::use_except))
1047       fail(error_code());
1048    #endif
1049    return result;
1050 }
1051
1052 template <class charT, class traits, class Allocator>
1053 re_detail::re_syntax_base* BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compile_set_aux(re_detail::jstack<traits_string_type, Allocator>& singles, re_detail::jstack<traits_string_type, Allocator>& ranges, re_detail::jstack<boost::uint_fast32_t, Allocator>& classes, re_detail::jstack<traits_string_type, Allocator>& equivalents, bool isnot, const re_detail::_wide_type&)
1054 {
1055    size_type base = data.size();
1056    data.extend(sizeof(re_detail::re_set_long));
1057    unsigned int csingles = 0;
1058    unsigned int cranges = 0;
1059    boost::uint_fast32_t cclasses = 0;
1060    unsigned int cequivalents = 0;
1061    bool nocollate_state = !(flags() & regex_constants::collate);
1062    bool singleton = true;
1063
1064    while(singles.empty() == false)
1065    {
1066       ++csingles;
1067       const traits_string_type& s = singles.peek();
1068       std::size_t len = (s.size() + 1) * sizeof(charT);
1069       if(len > sizeof(charT))
1070          singleton = false;
1071       std::memcpy(reinterpret_cast<charT*>(data.extend(len)), s.c_str(), len);
1072       singles.pop();
1073    }
1074    while(ranges.empty() == false)
1075    {
1076       traits_string_type c1, c2;
1077       if(nocollate_state)
1078          c1 = ranges.peek();
1079       else
1080          traits_inst.transform(c1, ranges.peek());
1081       ranges.pop();
1082       if(nocollate_state)
1083          c2 = ranges.peek();
1084       else
1085          traits_inst.transform(c2, ranges.peek());
1086       ranges.pop();
1087       if(c1 < c2)
1088       {
1089          // for some reason bc5 crashes when throwing exceptions
1090          // from here - probably an EH-compiler bug, but hard to
1091          // be sure...
1092          // delay throw to later:
1093          #ifdef __BORLANDC__
1094          boost::uint_fast32_t f = _flags;
1095          _flags &= ~regex_constants::use_except;
1096          #endif
1097          fail(REG_ERANGE);
1098          #ifdef __BORLANDC__
1099          _flags = f;
1100          #endif
1101          return 0;
1102       }
1103       ++cranges;
1104       std::size_t len = (re_detail::re_strlen(c1.c_str()) + 1) * sizeof(charT);
1105       std::memcpy(data.extend(len), c1.c_str(), len);
1106       len = (re_detail::re_strlen(c2.c_str()) + 1) * sizeof(charT);
1107       std::memcpy(data.extend(len), c2.c_str(), len);
1108    }
1109    while(classes.empty() == false)
1110    {
1111       cclasses |= classes.peek();
1112       classes.pop();
1113    }
1114    while(equivalents.empty() == false)
1115    {
1116       ++cequivalents;
1117       const traits_string_type& s = equivalents.peek();
1118       std::size_t len = (re_detail::re_strlen(s.c_str()) + 1) * sizeof(charT);
1119       std::memcpy(reinterpret_cast<charT*>(data.extend(len)), s.c_str(), len);
1120       equivalents.pop();
1121    }
1122
1123    re_detail::re_set_long* dat = reinterpret_cast<re_detail::re_set_long*>(reinterpret_cast<unsigned char*>(data.data()) + base);
1124    dat->type = re_detail::syntax_element_long_set;
1125    dat->csingles = csingles;
1126    dat->cranges = cranges;
1127    dat->cclasses = cclasses;
1128    dat->cequivalents = cequivalents;
1129    dat->isnot = isnot;
1130    dat->next.i = 0;
1131    dat->singleton = isnot ? true : singleton;
1132    return dat;
1133 }
1134
1135 template <class charT, class traits, class Allocator>
1136 re_detail::re_syntax_base* BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::compile_set_aux(re_detail::jstack<traits_string_type, Allocator>& singles, re_detail::jstack<traits_string_type, Allocator>& ranges, re_detail::jstack<boost::uint_fast32_t, Allocator>& classes, re_detail::jstack<traits_string_type, Allocator>& equivalents, bool isnot, const re_detail::_narrow_type&)
1137 {
1138    re_detail::re_set* dat = reinterpret_cast<re_detail::re_set*>(data.extend(sizeof(re_detail::re_set)));
1139    std::memset(dat, 0, sizeof(re_detail::re_set));
1140
1141    while(singles.empty() == false)
1142    {
1143       dat->_map[(traits_size_type)(traits_uchar_type)*(singles.peek().c_str())] = re_detail::mask_all;
1144       singles.pop();
1145    }
1146    while(ranges.empty() == false)
1147    {
1148       traits_string_type c1, c2, c3, c4;
1149
1150       if((flags() & regex_constants::collate) == 0)
1151          c1 = ranges.peek();
1152       else
1153          traits_inst.transform(c1, ranges.peek());
1154       ranges.pop();
1155       if((flags() & regex_constants::collate) == 0)
1156          c2 = ranges.peek();
1157       else
1158          traits_inst.transform(c2, ranges.peek());
1159       ranges.pop();
1160
1161       if(c1 < c2)
1162       {
1163          // for some reason bc5 crashes when throwing exceptions
1164          // from here - probably an EH-compiler bug, but hard to
1165          // be sure...
1166          // delay throw to later:
1167          #ifdef __BORLANDC__
1168          boost::uint_fast32_t f = _flags;
1169          _flags &= ~regex_constants::use_except;
1170          #endif
1171          fail(REG_ERANGE);
1172          #ifdef __BORLANDC__
1173          _flags = f;
1174          #endif
1175          return 0;
1176       }
1177       for(unsigned int i = 0; i < 256; ++i)
1178       {
1179          c4 = (charT)i;
1180          if((flags() & regex_constants::collate) == 0)
1181             c3 = c4;
1182          else
1183             traits_inst.transform(c3, c4);
1184          if((c3 <= c1) && (c3 >= c2))
1185             dat->_map[i] = re_detail::mask_all;
1186       }
1187    }
1188    while(equivalents.empty() == false)
1189    {
1190       traits_string_type c1, c2;
1191       for(unsigned int i = 0; i < 256; ++i)
1192       {
1193          c2 = (charT)i;
1194          traits_inst.transform_primary(c1, c2);
1195          if(c1 == equivalents.peek())
1196             dat->_map[i] = re_detail::mask_all;
1197       }
1198       equivalents.pop();
1199    }
1200
1201    boost::uint_fast32_t l_flags = 0;
1202    while(classes.empty() == false)
1203    {
1204       l_flags |= classes.peek();
1205       classes.pop();
1206    }
1207    if(l_flags)
1208    {
1209       for(unsigned int i = 0; i < 256; ++i)
1210       {
1211          if(traits_inst.is_class(charT(i), l_flags))
1212             dat->_map[(traits_uchar_type)traits_inst.translate((charT)i, (_flags & regex_constants::icase))] = re_detail::mask_all;
1213       }
1214    }
1215
1216    if(isnot)
1217    {
1218       for(unsigned int i = 0; i < 256; ++i)
1219       {
1220          dat->_map[i] = !dat->_map[i];
1221       }
1222    }
1223
1224    dat->type = re_detail::syntax_element_set;
1225    dat->next.i = 0;
1226    return dat;
1227 }
1228
1229 #ifndef __CODEGUARD__
1230 // this must not be inline when Borland's codeguard support is turned
1231 // on, otherwise we _will_ get surious codeguard errors...
1232 inline
1233 #endif
1234  re_detail::re_syntax_base* add_offset(void* base, std::ptrdiff_t off)
1235 {
1236    return reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<char*>(base) + off);
1237 }
1238
1239 template <class charT, class traits, class Allocator>
1240 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::fixup_apply(re_detail::re_syntax_base* b, unsigned cbraces)
1241 {
1242    typedef typename boost::detail::rebind_allocator<bool, Allocator>::type b_alloc;
1243
1244    register unsigned char* base = reinterpret_cast<unsigned char*>(b);
1245    register re_detail::re_syntax_base* ptr = b;
1246    bool* pb = 0;
1247    b_alloc a(data.allocator());
1248 #ifndef BOOST_NO_EXCEPTIONS
1249    try
1250    {
1251 #endif
1252       pb = a.allocate(cbraces);
1253       BOOST_REGEX_NOEH_ASSERT(pb)
1254       for(unsigned i = 0; i < cbraces; ++i)
1255          pb[i] = false;
1256
1257       repeats = 0;
1258
1259       while(ptr->next.i)
1260       {
1261          switch(ptr->type)
1262          {
1263          case re_detail::syntax_element_rep:
1264             jm_assert(data.size() > static_cast<re_detail::re_jump*>(ptr)->alt.i);
1265             static_cast<re_detail::re_jump*>(ptr)->alt.p = add_offset(base, static_cast<re_detail::re_jump*>(ptr)->alt.i);
1266 #ifdef BOOST_REGEX_DEBUG
1267             if((re_detail::padding_mask & reinterpret_cast<int>(static_cast<re_detail::re_jump*>(ptr)->alt.p)) && (static_cast<re_detail::re_jump*>(ptr)->alt.p != b))
1268             {
1269                jm_trace("padding mis-aligment in repeat jump to object type: " << static_cast<re_detail::re_jump*>(ptr)->alt.p->type)
1270                //jm_assert(0 == (padding_mask & (int)((re_detail::re_jump*)ptr)->alt.p));
1271             }
1272 #endif
1273             static_cast<re_detail::re_repeat*>(ptr)->id = repeats;
1274             ++repeats;
1275             goto rebase;
1276          case re_detail::syntax_element_jump:
1277          case re_detail::syntax_element_alt:
1278             jm_assert(data.size() > static_cast<re_detail::re_jump*>(ptr)->alt.i);
1279             static_cast<re_detail::re_jump*>(ptr)->alt.p = add_offset(base, static_cast<re_detail::re_jump*>(ptr)->alt.i);
1280 #ifdef BOOST_REGEX_DEBUG
1281             if((re_detail::padding_mask & reinterpret_cast<int>(static_cast<re_detail::re_jump*>(ptr)->alt.p) && (static_cast<re_detail::re_jump*>(ptr)->alt.p != b)))
1282             {
1283                jm_trace("padding mis-aligment in alternation jump to object type: " << static_cast<re_detail::re_jump*>(ptr)->alt.p->type)
1284                //jm_assert(0 == (padding_mask & (int)((re_detail::re_jump*)ptr)->alt.p));
1285             }
1286 #endif
1287             goto rebase;
1288          case re_detail::syntax_element_backref:
1289             if((static_cast<re_detail::re_brace*>(ptr)->index >= (int)cbraces) || (pb[static_cast<re_detail::re_brace*>(ptr)->index] == false) )
1290             {
1291                fail(REG_ESUBREG);
1292                a.deallocate(pb, cbraces);
1293                return;
1294             }
1295             goto rebase;
1296          case re_detail::syntax_element_endmark:
1297             if(static_cast<re_detail::re_brace*>(ptr)->index > 0)
1298                pb[static_cast<re_detail::re_brace*>(ptr)->index] = true;
1299             goto rebase;
1300          default:
1301             rebase:
1302             jm_assert(data.size() > ptr->next.i);
1303             ptr->next.p = add_offset(base, ptr->next.i);
1304 #ifdef BOOST_REGEX_DEBUG
1305             if((re_detail::padding_mask & (int)(ptr->next.p)) && (static_cast<re_detail::re_jump*>(ptr)->alt.p != b))
1306             {
1307                jm_trace("padding mis-alignment in next record of type " << ptr->next.p->type)
1308                jm_assert(0 == (re_detail::padding_mask & (int)(ptr->next.p)));
1309             }
1310 #endif
1311             ptr = ptr->next.p;
1312          }
1313       }
1314       a.deallocate(pb, cbraces);
1315       pb = 0;
1316 #ifndef BOOST_NO_EXCEPTIONS
1317    }
1318    catch(...)
1319    {
1320       if(pb)
1321          a.deallocate(pb, cbraces);
1322       throw;
1323    }
1324 #endif
1325 }
1326
1327
1328 template <class charT, class traits, class Allocator>
1329 unsigned int BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::set_expression(const charT* arg_first, const charT* arg_last, flag_type f)
1330 {
1331 # ifdef BOOST_MSVC
1332 #  pragma warning(push)
1333 #  pragma warning(disable: 4127)
1334 #endif
1335 #ifdef __OpenBSD__
1336    // strxfrm not working on OpenBSD??
1337    f &= ~regex_constants::collate;
1338 #endif
1339
1340    if(arg_first == expression())
1341    {
1342       traits_string_type s(arg_first, arg_last);
1343       return set_expression(s.c_str(), s.c_str() + s.size(), f);
1344    }
1345    typedef typename traits_type::sentry sentry_t;
1346    sentry_t sent(traits_inst);
1347    if(sent){
1348
1349    const charT* base = arg_first;
1350    data.clear();
1351    _flags = f;
1352    fail(REG_NOERROR);  // clear any error
1353
1354    if(arg_first >= arg_last)
1355    {
1356       fail(REG_EMPTY);
1357       return error_code();
1358    }
1359
1360    const charT* ptr = arg_first;
1361    marks = 0;
1362    re_detail::jstack<std::size_t, Allocator> mark(64, data.allocator());
1363    re_detail::jstack<int, Allocator> markid(64, data.allocator());
1364    std::size_t last_mark_popped = 0;
1365    register traits_size_type c;
1366    register re_detail::re_syntax_base* dat;
1367
1368    unsigned rep_min = 0;
1369    unsigned rep_max = 0;
1370
1371    //
1372    // set up header:
1373    //
1374    ++marks;
1375    dat = 0;
1376
1377    if(_flags & regex_constants::literal)
1378    {
1379       while(ptr != arg_last)
1380       {
1381          dat = add_literal(dat, traits_inst.translate(*ptr, (_flags & regex_constants::icase)));
1382          ++ptr;
1383       }
1384    }
1385
1386    while (ptr < arg_last)
1387    {
1388       c = (traits_size_type)(traits_uchar_type)*ptr;
1389       // this is only used for the switch(), but cannot be folded in
1390       // due to a bug in Comeau 4.2.44beta3
1391       traits_size_type syntax = traits_inst.syntax_type(c);
1392       switch(syntax)
1393       {
1394       case traits_type::syntax_open_bracket:
1395          if(_flags & bk_parens)
1396          {
1397             dat = add_literal(dat, (charT)c);
1398             ++ptr;
1399             continue;
1400          }
1401          open_bracked_jump:
1402          // extend:
1403          dat = add_simple(dat, re_detail::syntax_element_startmark, sizeof(re_detail::re_brace));
1404          if(_flags & nosubs)
1405          {
1406             markid.push(0);
1407             static_cast<re_detail::re_brace*>(dat)->index = 0;
1408          }
1409          else
1410          {
1411             markid.push(marks);
1412             static_cast<re_detail::re_brace*>(dat)->index = marks++;
1413          }
1414          mark.push(data.index(dat));
1415          ++ptr;
1416          //
1417          // check for perl like (?...) extention syntax
1418          c = (traits_size_type)(traits_uchar_type)*ptr;
1419          if(((_flags & (bk_parens|perlex)) == perlex) && (traits_type::syntax_question == traits_inst.syntax_type(c)))
1420          {
1421             ++ptr;
1422             c = (traits_size_type)(traits_uchar_type)*ptr;
1423             // this is only used for the switch(), but cannot be folded in
1424             // due to a bug in Comeau 4.2.44beta3
1425             traits_size_type syntax2 = traits_inst.syntax_type(c);
1426             switch(syntax2)
1427             {
1428             case traits_type::syntax_colon:
1429                static_cast<re_detail::re_brace*>(dat)->index = 0;
1430                --marks;
1431                markid.pop();
1432                markid.push(0);
1433                ++ptr;
1434                continue;
1435             case traits_type::syntax_equal:
1436                static_cast<re_detail::re_brace*>(dat)->index = -1;
1437                markid.pop();
1438                markid.push(-1);
1439                common_forward_assert:
1440                --marks;
1441                ++ptr;
1442                // extend:
1443                dat = add_simple(dat, re_detail::syntax_element_jump, re_detail::re_jump_size);
1444                data.align();
1445                //
1446                // we don't know what value to put here yet,
1447                // use an arbitrarily large value for now
1448                // and check it later:
1449                static_cast<re_detail::re_jump*>(dat)->alt.i = INT_MAX/2;
1450                mark.push(data.size() - re_detail::re_jump_size);
1451                continue;
1452             case traits_type::syntax_right_word:
1453                static_cast<re_detail::re_brace*>(dat)->index = -3;
1454                markid.pop();
1455                markid.push(-3);
1456                goto common_forward_assert;
1457             case traits_type::syntax_not:
1458                static_cast<re_detail::re_brace*>(dat)->index = -2;
1459                markid.pop();
1460                markid.push(-2);
1461                goto common_forward_assert;
1462             case traits_type::syntax_hash:
1463                // comment just skip it:
1464                static_cast<re_detail::re_brace*>(dat)->index = 0;
1465                --marks;
1466                markid.pop();
1467                mark.pop();
1468                do{
1469                   ++ptr;
1470                   c = (traits_size_type)(traits_uchar_type)*ptr;
1471                }while(traits_type::syntax_close_bracket != traits_inst.syntax_type(c));
1472                ++ptr;
1473                continue;
1474             default:
1475                //
1476                // error, return to standard parsing and let that handle the error:
1477                --ptr;
1478                continue;
1479             }
1480          }
1481          break;
1482       case traits_type::syntax_close_bracket:
1483          if(_flags & bk_parens)
1484          {
1485             dat = add_literal(dat, (charT)c);
1486             ++ptr;
1487             continue;
1488          }
1489
1490          close_bracked_jump:
1491          if(dat)
1492          {
1493             data.align();
1494             dat->next.i = data.size();
1495          }
1496
1497          if(mark.empty())
1498          {
1499             fail(REG_EPAREN);
1500             return error_code();
1501          }
1502          // see if we have an empty alternative:
1503          if(mark.peek() == data.index(dat) )
1504          {
1505             re_detail::re_syntax_base* para = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<char*>(data.data()) + mark.peek());
1506             if(para->type == re_detail::syntax_element_jump)
1507             {
1508                fail(REG_EMPTY);
1509                return error_code();
1510             }
1511          }
1512
1513          // pop any pushed alternatives and set the target arg_last destination:
1514          dat = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<unsigned char*>(data.data()) + mark.peek());
1515          while(dat->type == re_detail::syntax_element_jump)
1516          {
1517             static_cast<re_detail::re_jump*>(dat)->alt.i = data.size();
1518             mark.pop();
1519             if(mark.empty())
1520             {
1521                fail(REG_EPAREN);
1522                return error_code();
1523             }
1524             dat = reinterpret_cast<re_detail::re_jump*>(reinterpret_cast<unsigned char*>(data.data()) + mark.peek());
1525          }
1526
1527          dat = add_simple(0, re_detail::syntax_element_endmark, sizeof(re_detail::re_brace));
1528          static_cast<re_detail::re_brace*>(dat)->index = markid.peek();
1529          markid.pop();
1530          last_mark_popped = mark.peek();
1531          mark.pop();
1532          ++ptr;
1533          break;
1534       case traits_type::syntax_char:
1535          dat = add_literal(dat, (charT)c);
1536          ++ptr;
1537          break;
1538       case traits_type::syntax_slash:
1539       {
1540          if(++ptr == arg_last)
1541          {
1542             fail(REG_EESCAPE);
1543             return error_code();
1544          }
1545          c = (traits_size_type)(traits_uchar_type)*ptr;
1546          // this is only used for the switch(), but cannot be folded in
1547          // due to a bug in Comeau 4.2.44beta3
1548          traits_size_type syntax3 = traits_inst.syntax_type(c);
1549          switch(syntax3)
1550          {
1551          case traits_type::syntax_open_bracket:
1552             if(_flags & bk_parens)
1553                goto open_bracked_jump;
1554             break;
1555          case traits_type::syntax_close_bracket:
1556             if(_flags & bk_parens)
1557                goto close_bracked_jump;
1558             break;
1559          case traits_type::syntax_plus:
1560             if((_flags & bk_plus_qm) && ((_flags & limited_ops) == 0))
1561             {
1562                rep_min = 1;
1563                rep_max = (unsigned)-1;
1564                goto repeat_jump;
1565             }
1566             break;
1567          case traits_type::syntax_question:
1568             if((_flags & bk_plus_qm) && ((_flags & limited_ops) == 0))
1569             {
1570                rep_min = 0;
1571                rep_max = 1;
1572                goto repeat_jump;
1573             }
1574             break;
1575          case traits_type::syntax_or:
1576             if(((_flags & bk_vbar) == 0) || (_flags & limited_ops))
1577                break;
1578             goto alt_string_jump;
1579          case traits_type::syntax_open_brace:
1580             if( ((_flags & bk_braces) == 0) || ((_flags & intervals) == 0))
1581                break;
1582
1583             // we have {x} or {x,} or {x,y}:
1584             parse_range(ptr, arg_last, rep_min, rep_max);
1585             goto repeat_jump;
1586
1587          case traits_type::syntax_digit:
1588             if(_flags & bk_refs)
1589             {
1590                // update previous:
1591                int i = traits_inst.toi((charT)c);
1592                if(i == 0)
1593                {
1594                   // we can have \025 which means take char whose
1595                   // code is 25 (octal), so parse string:
1596                   c = traits_inst.toi(ptr, arg_last, -8);
1597                   --ptr;
1598                   break;
1599                }
1600                dat = add_simple(dat, re_detail::syntax_element_backref, sizeof(re_detail::re_brace));
1601                static_cast<re_detail::re_brace*>(dat)->index = i;
1602                ++ptr;
1603                continue;
1604             }
1605             break;
1606          case traits_type::syntax_b:     // re_detail::syntax_element_word_boundary
1607             dat = add_simple(dat, re_detail::syntax_element_word_boundary);
1608             ++ptr;
1609             continue;
1610          case traits_type::syntax_B:
1611             dat = add_simple(dat, re_detail::syntax_element_within_word);
1612             ++ptr;
1613             continue;
1614          case traits_type::syntax_left_word:
1615             dat = add_simple(dat, re_detail::syntax_element_word_start);
1616             ++ptr;
1617             continue;
1618          case traits_type::syntax_right_word:
1619             dat = add_simple(dat, re_detail::syntax_element_word_end);
1620             ++ptr;
1621             continue;
1622          case traits_type::syntax_w:     //re_detail::syntax_element_word_char
1623             dat = compile_set_simple(dat, traits_type::char_class_word);
1624             ++ptr;
1625             continue;
1626          case traits_type::syntax_W:
1627             dat = compile_set_simple(dat, traits_type::char_class_word, true);
1628             ++ptr;
1629             continue;
1630          case traits_type::syntax_d:     //re_detail::syntax_element_word_char
1631             dat = compile_set_simple(dat, traits_type::char_class_digit);
1632             ++ptr;
1633             continue;
1634          case traits_type::syntax_D:
1635             dat = compile_set_simple(dat, traits_type::char_class_digit, true);
1636             ++ptr;
1637             continue;
1638          case traits_type::syntax_s:     //re_detail::syntax_element_word_char
1639             dat = compile_set_simple(dat, traits_type::char_class_space);
1640             ++ptr;
1641             continue;
1642          case traits_type::syntax_S:
1643             dat = compile_set_simple(dat, traits_type::char_class_space, true);
1644             ++ptr;
1645             continue;
1646          case traits_type::syntax_l:     //re_detail::syntax_element_word_char
1647             dat = compile_set_simple(dat, traits_type::char_class_lower);
1648             ++ptr;
1649             continue;
1650          case traits_type::syntax_L:
1651             dat = compile_set_simple(dat, traits_type::char_class_lower, true);
1652             ++ptr;
1653             continue;
1654          case traits_type::syntax_u:     //re_detail::syntax_element_word_char
1655             dat = compile_set_simple(dat, traits_type::char_class_upper);
1656             ++ptr;
1657             continue;
1658          case traits_type::syntax_U:
1659             dat = compile_set_simple(dat, traits_type::char_class_upper, true);
1660             ++ptr;
1661             continue;
1662          case traits_type::syntax_Q:
1663             ++ptr;
1664             while(true)
1665             {
1666                if(ptr == arg_last)
1667                {
1668                   fail(REG_EESCAPE);
1669                   return error_code();
1670                }
1671                if(traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) == traits_type::syntax_slash)
1672                {
1673                   ++ptr;
1674                   if((ptr != arg_last) && (traits_inst.syntax_type((traits_size_type)(traits_uchar_type)*ptr) == traits_type::syntax_E))
1675                      break;
1676                   else
1677                   {
1678                      dat = add_literal(dat, *(ptr-1));
1679                      continue;
1680                   }
1681                }
1682                dat = add_literal(dat, *ptr);
1683                ++ptr;
1684             }
1685             ++ptr;
1686             continue;
1687          case traits_type::syntax_C:
1688             dat = add_simple(dat, re_detail::syntax_element_wild);
1689             ++ptr;
1690             continue;
1691          case traits_type::syntax_X:
1692             dat = add_simple(dat, re_detail::syntax_element_combining);
1693             ++ptr;
1694             continue;
1695          case traits_type::syntax_Z:
1696             dat = add_simple(dat, re_detail::syntax_element_soft_buffer_end);
1697             ++ptr;
1698             continue;
1699          case traits_type::syntax_G:
1700             dat = add_simple(dat, re_detail::syntax_element_restart_continue);
1701             ++ptr;
1702             continue;
1703          case traits_type::syntax_start_buffer:
1704             dat = add_simple(dat, re_detail::syntax_element_buffer_start);
1705             ++ptr;
1706             continue;
1707          case traits_type::syntax_end_buffer:
1708             dat = add_simple(dat, re_detail::syntax_element_buffer_end);
1709             ++ptr;
1710             continue;
1711          default:
1712             c = (traits_size_type)(traits_uchar_type)parse_escape(ptr, arg_last);
1713             dat = add_literal(dat, (charT)c);
1714             continue;
1715          }
1716          dat = add_literal(dat, (charT)c);
1717          ++ptr;
1718          break;
1719       }
1720       case traits_type::syntax_dollar:
1721          dat = add_simple(dat, re_detail::syntax_element_end_line, sizeof(re_detail::re_syntax_base));
1722          ++ptr;
1723          continue;
1724       case traits_type::syntax_caret:
1725          dat = add_simple(dat, re_detail::syntax_element_start_line, sizeof(re_detail::re_syntax_base));
1726          ++ptr;
1727          continue;
1728       case traits_type::syntax_dot:
1729          dat = add_simple(dat, re_detail::syntax_element_wild, sizeof(re_detail::re_syntax_base));
1730          ++ptr;
1731          continue;
1732       case traits_type::syntax_star:
1733          rep_min = 0;
1734          rep_max = (unsigned)-1;
1735
1736          repeat_jump:
1737          {
1738           std::ptrdiff_t offset;
1739             if(dat == 0)
1740             {
1741                fail(REG_BADRPT);
1742                return error_code();
1743             }
1744             switch(dat->type)
1745             {
1746             case re_detail::syntax_element_endmark:
1747                offset = last_mark_popped;
1748                break;
1749             case re_detail::syntax_element_literal:
1750                if(static_cast<re_detail::re_literal*>(dat)->length > 1)
1751                {
1752                   // update previous:
1753                   charT lit = *reinterpret_cast<charT*>(reinterpret_cast<char*>(dat) + sizeof(re_detail::re_literal) + ((static_cast<re_detail::re_literal*>(dat)->length-1)*sizeof(charT)));
1754                   --static_cast<re_detail::re_literal*>(dat)->length;
1755                   dat = add_simple(dat, re_detail::syntax_element_literal, sizeof(re_detail::re_literal) + sizeof(charT));
1756                   static_cast<re_detail::re_literal*>(dat)->length = 1;
1757                   *reinterpret_cast<charT*>(static_cast<re_detail::re_literal*>(dat)+1) = lit;
1758                }
1759                offset = reinterpret_cast<char*>(dat) - reinterpret_cast<char*>(data.data());
1760                break;
1761             case re_detail::syntax_element_backref:
1762             case re_detail::syntax_element_long_set:
1763             case re_detail::syntax_element_set:
1764             case re_detail::syntax_element_wild:
1765             case re_detail::syntax_element_combining:
1766                // we're repeating a single item:
1767                offset = reinterpret_cast<char*>(dat) - reinterpret_cast<char*>(data.data());
1768                break;
1769             default:
1770                fail(REG_BADRPT);
1771                return error_code();
1772             }
1773             data.align();
1774             dat->next.i = data.size();
1775             //unsigned pos = (char*)dat - (char*)data.data();
1776
1777             // add the trailing jump:
1778             dat = add_simple(dat, re_detail::syntax_element_jump, re_detail::re_jump_size);
1779             static_cast<re_detail::re_jump*>(dat)->alt.i = 0;
1780
1781             // now insert the leading repeater:
1782             dat = static_cast<re_detail::re_syntax_base*>(data.insert(offset, re_detail::re_repeater_size));
1783             dat->next.i = (reinterpret_cast<char*>(dat) - reinterpret_cast<char*>(data.data())) + re_detail::re_repeater_size;
1784             dat->type = re_detail::syntax_element_rep;
1785             static_cast<re_detail::re_repeat*>(dat)->alt.i = data.size();
1786             static_cast<re_detail::re_repeat*>(dat)->min = rep_min;
1787             static_cast<re_detail::re_repeat*>(dat)->max = rep_max;
1788             static_cast<re_detail::re_repeat*>(dat)->leading = false;
1789             static_cast<re_detail::re_repeat*>(dat)->greedy = true;
1790             move_offsets(dat, re_detail::re_repeater_size);
1791             ++ptr;
1792             //
1793             // now check to see if we have a non-greedy repeat:
1794             if((ptr != arg_last) && (_flags & (perlex | limited_ops | bk_plus_qm | bk_braces)) == perlex)
1795             {
1796                c = (traits_size_type)(traits_uchar_type)*ptr;
1797                if(traits_type::syntax_question == traits_inst.syntax_type(c))
1798                {
1799                   // OK repeat is non-greedy:
1800                   static_cast<re_detail::re_repeat*>(dat)->greedy = false;
1801                   ++ptr;
1802                }
1803             }
1804             dat = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<char*>(data.data()) + data.size() - re_detail::re_jump_size);
1805             static_cast<re_detail::re_repeat*>(dat)->alt.i = offset;
1806             continue;
1807          }
1808       case traits_type::syntax_plus:
1809          if(_flags & (bk_plus_qm | limited_ops))
1810          {
1811             dat = add_literal(dat, (charT)c);
1812             ++ptr;
1813             continue;
1814          }
1815          rep_min = 1;
1816          rep_max = (unsigned)-1;
1817          goto repeat_jump;
1818       case traits_type::syntax_question:
1819          if(_flags & (bk_plus_qm | limited_ops))
1820          {
1821             dat = add_literal(dat, (charT)c);
1822             ++ptr;
1823             continue;
1824          }
1825          rep_min = 0;
1826          rep_max = 1;
1827          goto repeat_jump;
1828       case traits_type::syntax_open_set:
1829          // update previous:
1830          if(dat)
1831          {
1832             data.align();
1833             dat->next.i = data.size();
1834          }
1835          // extend:
1836          dat = compile_set(ptr, arg_last);
1837          if(dat == 0)
1838          {
1839             if((_flags & regex_constants::failbit) == 0)
1840                fail(REG_EBRACK);
1841             return error_code();
1842          }
1843          break;
1844       case traits_type::syntax_or:
1845       {
1846          if(_flags & (bk_vbar | limited_ops))
1847          {
1848             dat = add_literal(dat, (charT)c);
1849             ++ptr;
1850             continue;
1851          }
1852
1853          alt_string_jump:
1854
1855          // update previous:
1856          if(dat == 0)
1857          {
1858             // start of pattern can't have empty "|"
1859             fail(REG_EMPTY);
1860             return error_code();
1861          }
1862          // see if we have an empty alternative:
1863          if(mark.empty() == false)
1864             if(mark.peek() == data.index(dat))
1865             {
1866                fail(REG_EMPTY);
1867                return error_code();
1868             }
1869          // extend:
1870          dat = add_simple(dat, re_detail::syntax_element_jump, re_detail::re_jump_size);
1871          data.align();
1872          //
1873          // we don't know what value to put here yet,
1874          // use an arbitrarily large value for now
1875          // and check it later (TODO!)
1876          static_cast<re_detail::re_jump*>(dat)->alt.i = INT_MAX/2;
1877
1878          // now work out where to insert:
1879          std::size_t offset = 0;
1880          if(mark.empty() == false)
1881          {
1882             // we have a '(' or '|' to go back to:
1883             offset = mark.peek();
1884             re_detail::re_syntax_base* base2 = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<unsigned char*>(data.data()) + offset);
1885             offset = base2->next.i;
1886          }
1887          re_detail::re_jump* j = static_cast<re_detail::re_jump*>(data.insert(offset, re_detail::re_jump_size));
1888          j->type = re_detail::syntax_element_alt;
1889          j->next.i = offset + re_detail::re_jump_size;
1890          j->alt.i = data.size();
1891          move_offsets(j, re_detail::re_jump_size);
1892          dat = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<unsigned char*>(data.data()) + data.size() - re_detail::re_jump_size);
1893          mark.push(data.size() - re_detail::re_jump_size);
1894          ++ptr;
1895          break;
1896       }
1897       case traits_type::syntax_open_brace:
1898          if((_flags & bk_braces) || ((_flags & intervals) == 0))
1899          {
1900             dat = add_literal(dat, (charT)c);
1901             ++ptr;
1902             continue;
1903          }
1904          // we have {x} or {x,} or {x,y}:
1905          parse_range(ptr, arg_last, rep_min, rep_max);
1906          goto repeat_jump;
1907       case traits_type::syntax_newline:
1908          if(_flags & newline_alt)
1909             goto alt_string_jump;
1910          dat = add_literal(dat, (charT)c);
1911          ++ptr;
1912          continue;
1913       case traits_type::syntax_close_brace:
1914          if(_flags & bk_braces)
1915          {
1916             dat = add_literal(dat, (charT)c);
1917             ++ptr;
1918             continue;
1919          }
1920          fail(REG_BADPAT);
1921          return error_code();
1922       default:
1923          dat = add_literal(dat, (charT)c);
1924          ++ptr;
1925          break;
1926       }  // switch
1927    }     // while
1928
1929    //
1930    // update previous:
1931    if(dat)
1932    {
1933       data.align();
1934       dat->next.i = data.size();
1935    }
1936
1937    // see if we have an empty alternative:
1938    if(mark.empty() == false)
1939       if(mark.peek() == data.index(dat) )
1940       {
1941          re_detail::re_syntax_base* para = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<char*>(data.data()) + mark.peek());
1942          if(para->type == re_detail::syntax_element_jump)
1943          {
1944             fail(REG_EMPTY);
1945             return error_code();
1946          }
1947       }
1948    //
1949    // set up tail:
1950    //
1951    if(mark.empty() == false)
1952    {
1953       // pop any pushed alternatives and set the target arg_last destination:
1954       dat = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<unsigned char*>(data.data()) + mark.peek());
1955       while(dat->type == re_detail::syntax_element_jump)
1956       {
1957          static_cast<re_detail::re_jump*>(dat)->alt.i = data.size();
1958          mark.pop();
1959          if(mark.empty() == true)
1960             break;
1961          dat = reinterpret_cast<re_detail::re_jump*>(reinterpret_cast<unsigned char*>(data.data()) + mark.peek());
1962       }
1963    }
1964
1965    dat = static_cast<re_detail::re_brace*>(data.extend(sizeof(re_detail::re_syntax_base)));
1966    dat->type = re_detail::syntax_element_match;
1967    dat->next.i = 0;
1968
1969    if(mark.empty() == false)
1970    {
1971       fail(REG_EPAREN);
1972       return error_code();
1973    }
1974
1975    //
1976    // allocate space for start _map:
1977    startmap = reinterpret_cast<unsigned char*>(data.extend(256 + ((arg_last - base + 1) * sizeof(charT))));
1978    //
1979    // and copy the expression we just compiled:
1980    _expression = reinterpret_cast<charT*>(reinterpret_cast<char*>(startmap) + 256);
1981    _expression_len = arg_last - base;
1982    std::memcpy(_expression, base, _expression_len * sizeof(charT));
1983    *(_expression + _expression_len) = charT(0);
1984
1985    //
1986    // now we need to apply fixups to the array
1987    // so that we can use pointers and not indexes
1988    fixup_apply(static_cast<re_detail::re_syntax_base*>(data.data()), marks);
1989
1990    // check for error during fixup:
1991    if(_flags & regex_constants::failbit)
1992       return error_code();
1993
1994    //
1995    // finally compile the maps so that we can make intelligent choices
1996    // whenever we encounter an alternative:
1997    compile_maps();
1998    if(pkmp)
1999    {
2000       re_detail::kmp_free(pkmp, data.allocator());
2001       pkmp = 0;
2002    }
2003    re_detail::re_syntax_base* sbase = static_cast<re_detail::re_syntax_base*>(data.data());
2004    _restart_type = probe_restart(sbase);
2005    _leading_len = fixup_leading_rep(sbase, 0);
2006    if((sbase->type == re_detail::syntax_element_literal) && (sbase->next.p->type == re_detail::syntax_element_match))
2007    {
2008       _restart_type = restart_fixed_lit;
2009       if(0 == pkmp)
2010       {
2011          charT* p1 = reinterpret_cast<charT*>(reinterpret_cast<char*>(sbase) + sizeof(re_detail::re_literal));
2012          charT* p2 = p1 + static_cast<re_detail::re_literal*>(sbase)->length;
2013          pkmp = re_detail::kmp_compile(p1, p2, charT(), re_detail::kmp_translator<traits>(_flags&regex_constants::icase, &traits_inst), data.allocator());
2014       }
2015    }
2016    return error_code();
2017
2018    } // sentry
2019    return REG_EMPTY;
2020
2021 # ifdef BOOST_MSVC
2022 #  pragma warning(pop)
2023 #endif
2024
2025 }
2026
2027 template <class charT, class traits, class Allocator>
2028 re_detail::re_syntax_base* BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::add_simple(re_detail::re_syntax_base* dat, re_detail::syntax_element_type type, unsigned int arg_size)
2029 {
2030    if(dat)
2031    {
2032       data.align();
2033       dat->next.i = data.size();
2034    }
2035    if(arg_size < sizeof(re_detail::re_syntax_base))
2036       arg_size = sizeof(re_detail::re_syntax_base);
2037    dat = static_cast<re_detail::re_syntax_base*>(data.extend(arg_size));
2038    dat->type = type;
2039    dat->next.i = 0;
2040    return dat;
2041 }
2042
2043 template <class charT, class traits, class Allocator>
2044 re_detail::re_syntax_base* BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::add_literal(re_detail::re_syntax_base* dat, charT c)
2045 {
2046    if(dat && (dat->type == re_detail::syntax_element_literal))
2047    {
2048       // add another charT to the list:
2049       std::ptrdiff_t pos = reinterpret_cast<unsigned char*>(dat) - reinterpret_cast<unsigned char*>(data.data());
2050       *reinterpret_cast<charT*>(data.extend(sizeof(charT))) = traits_inst.translate(c, (_flags & regex_constants::icase));
2051       dat = reinterpret_cast<re_detail::re_syntax_base*>(reinterpret_cast<unsigned char*>(data.data()) + pos);
2052       ++(static_cast<re_detail::re_literal*>(dat)->length);
2053    }
2054    else
2055    {
2056       // extend:
2057       dat = add_simple(dat, re_detail::syntax_element_literal, sizeof(re_detail::re_literal) + sizeof(charT));
2058       static_cast<re_detail::re_literal*>(dat)->length = 1;
2059       *reinterpret_cast<charT*>(reinterpret_cast<re_detail::re_literal*>(dat)+1) = traits_inst.translate(c, (_flags & regex_constants::icase));
2060    }
2061    return dat;
2062 }
2063
2064 template <class charT, class traits, class Allocator>
2065 unsigned int BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::probe_restart(re_detail::re_syntax_base* dat)
2066 {
2067    switch(dat->type)
2068    {
2069    case re_detail::syntax_element_startmark:
2070    case re_detail::syntax_element_endmark:
2071       if(static_cast<const re_detail::re_brace*>(dat)->index == -2)
2072          return regbase::restart_any;
2073       return probe_restart(dat->next.p);
2074    case re_detail::syntax_element_start_line:
2075       return regbase::restart_line;
2076    case re_detail::syntax_element_word_start:
2077       return regbase::restart_word;
2078    case re_detail::syntax_element_buffer_start:
2079       return regbase::restart_buf;
2080    case re_detail::syntax_element_restart_continue:
2081       return regbase::restart_continue;
2082    default:
2083       return regbase::restart_any;
2084    }
2085 }
2086
2087 template <class charT, class traits, class Allocator>
2088 unsigned int BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::fixup_leading_rep(re_detail::re_syntax_base* dat, re_detail::re_syntax_base* arg_end)
2089 {
2090    unsigned int len = 0;
2091    bool leading_lit = arg_end ? false : true;
2092    while(dat != arg_end)
2093    {
2094       switch(dat->type)
2095       {
2096       case re_detail::syntax_element_literal:
2097          len += static_cast<re_detail::re_literal*>(dat)->length;
2098          if((leading_lit) && (static_cast<re_detail::re_literal*>(dat)->length > 2))
2099          {
2100             // we can do a literal search for the leading literal string
2101             // using Knuth-Morris-Pratt (or whatever), and only then check for
2102             // matches.  We need a decent length string though to make it
2103             // worth while.
2104             _leading_string = reinterpret_cast<charT*>(reinterpret_cast<char*>(dat) + sizeof(re_detail::re_literal));
2105             _leading_string_len = static_cast<re_detail::re_literal*>(dat)->length;
2106             _restart_type = restart_lit;
2107             leading_lit = false;
2108             const charT* p1 = _leading_string;
2109             const charT* p2 = _leading_string + _leading_string_len;
2110             pkmp = re_detail::kmp_compile(p1, p2, charT(), re_detail::kmp_translator<traits>(_flags&regex_constants::icase, &traits_inst), data.allocator());
2111          }
2112          leading_lit = false;
2113          break;
2114       case re_detail::syntax_element_wild:
2115          ++len;
2116          leading_lit = false;
2117          break;
2118       case re_detail::syntax_element_match:
2119          return len;
2120       case re_detail::syntax_element_backref:
2121       //case re_detail::syntax_element_jump:
2122       case re_detail::syntax_element_alt:
2123       case re_detail::syntax_element_combining:
2124          return 0;
2125       case re_detail::syntax_element_long_set:
2126       {
2127          // we need to verify that there are no multi-character
2128          // collating elements inside the repeat:
2129          if(!static_cast<re_detail::re_set_long*>(dat)->singleton)
2130             return 0;
2131          ++len;
2132          leading_lit = false;
2133          break;
2134       }
2135       case re_detail::syntax_element_set:
2136          ++len;
2137          leading_lit = false;
2138          break;
2139       case re_detail::syntax_element_rep:
2140       case re_detail::syntax_element_dot_rep:
2141       case re_detail::syntax_element_char_rep:
2142       case re_detail::syntax_element_short_set_rep:
2143       case re_detail::syntax_element_long_set_rep:
2144          if((len == 0) && (1 == fixup_leading_rep(dat->next.p, static_cast<re_detail::re_repeat*>(dat)->alt.p) ))
2145          {
2146             static_cast<re_detail::re_repeat*>(dat)->leading = leading_lit;
2147             return len;
2148          }
2149          return len;
2150      case re_detail::syntax_element_startmark:
2151          if(static_cast<const re_detail::re_brace*>(dat)->index == -2)
2152             return 0;
2153          // fall through:
2154       default:
2155          break;
2156       }
2157       dat = dat->next.p;
2158    }
2159    return len;
2160 }
2161
2162 template <class charT, class traits, class Allocator>
2163 void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::fail(unsigned int err)
2164 {
2165    error_code_  = err;
2166    if(err)
2167    {
2168       _flags |= regex_constants::failbit;
2169 #ifndef BOOST_NO_EXCEPTIONS
2170       if(_flags & regex_constants::use_except)
2171       {
2172          re_detail::raise_error(traits_inst, err);
2173       }
2174 #endif
2175    }
2176    else
2177       _flags &= ~regex_constants::failbit;
2178 }
2179
2180 #ifdef __BORLANDC__
2181 #pragma option pop
2182 #endif
2183 #ifdef BOOST_HAS_ABI_HEADERS
2184 #  include BOOST_ABI_SUFFIX
2185 #endif
2186
2187 } // namespace boost
2188
2189
2190 #endif   // BOOST_REGEX_COMPILE_HPP
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201