boost/boost/re_detail/regex_compile.hpp

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