boost/boost/regex.hpp

   1 /*
   2  *
   3  * Copyright (c) 1998-2002
   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.cpp
  19   *   VERSION      see <boost/version.hpp>
  20   *   DESCRIPTION: Declares boost::reg_expression<> and associated
  21   *                functions and classes. This header is the main
  22   *                entry point for the template regex code.
  23   */
  24
  25
  26 /* start with C compatibility API */
  27
  28 #ifndef BOOST_RE_REGEX_HPP
  29 #define BOOST_RE_REGEX_HPP
  30
  31 #include <boost/cregex.hpp>
  32
  33 #ifdef __cplusplus
  34
  35 // what follows is all C++ don't include in C builds!!
  36
  37 #ifdef BOOST_REGEX_DEBUG
  38 # include <iosfwd>
  39 #endif
  40
  41 #include <new>
  42 #include <boost/regex/config.hpp>
  43 #include <cstring>
  44 #include <boost/regex_fwd.hpp>
  45 #include <boost/regex/detail/regex_stack.hpp>
  46 #include <boost/regex/detail/regex_raw_buffer.hpp>
  47 #include <boost/regex/detail/regex_kmp.hpp>
  48 #include <boost/regex/pattern_except.hpp>
  49 #include <boost/regex/regex_traits.hpp>
  50 #include <boost/type_traits/cv_traits.hpp>
  51 #include <boost/scoped_array.hpp>
  52
  53
  54 namespace boost{
  55
  56 #ifdef __BORLANDC__
  57    #pragma option push -a8 -b -Vx -Ve -pc -w-8027
  58 #endif
  59
  60 namespace re_detail{
  61
  62 struct re_set_long;
  63 struct re_syntax_base;
  64
  65 } // namespace re_detail
  66
  67 namespace deprecated{
  68 //
  69 // class char_regex_traits_i
  70 // provides case insensitive traits classes (deprecated):
  71 template <class charT>
  72 class char_regex_traits_i : public regex_traits<charT> {};
  73
  74 template<>
  75 class char_regex_traits_i<char> : public regex_traits<char>
  76 {
  77 public:
  78    typedef char char_type;
  79    typedef unsigned char uchar_type;
  80    typedef unsigned int size_type;
  81    typedef regex_traits<char> base_type;
  82
  83    char BOOST_REGEX_CALL translate(char c, bool)const
  84    {
  85       return static_cast<const regex_traits<char>*>(this)->translate(c, true);
  86    }
  87 };
  88
  89 #ifndef BOOST_NO_WREGEX
  90 template<>
  91 class char_regex_traits_i<wchar_t> : public regex_traits<wchar_t>
  92 {
  93 public:
  94    typedef wchar_t char_type;
  95    typedef unsigned short uchar_type;
  96    typedef unsigned int size_type;
  97    typedef regex_traits<wchar_t> base_type;
  98
  99    wchar_t BOOST_REGEX_CALL translate(wchar_t c, bool)const
 100    {
 101       return static_cast<const regex_traits<wchar_t>*>(this)->translate(c, true);
 102    }
 103    boost::uint_fast32_t BOOST_REGEX_CALL lookup_classname(const wchar_t* first, const wchar_t* last)const
 104    {
 105       boost::uint_fast32_t result = static_cast<const regex_traits<wchar_t>*>(this)->lookup_classname(first, last);
 106       if((result & base_type::char_class_upper) == base_type::char_class_upper)
 107          result |= base_type::char_class_alpha;
 108       return result;
 109    }
 110 };
 111 #endif
 112 } // namespace deprecated
 113
 114
 115 namespace re_detail{
 116
 117 enum mask_type
 118 {
 119    mask_take = 1,
 120    mask_skip = 2,
 121    mask_any = mask_skip | mask_take,
 122    mask_all = mask_any
 123 };
 124
 125 struct _narrow_type{};
 126 struct _wide_type{};
 127
 128 template <class charT>
 129 class is_byte;
 130
 131 template<>
 132 class is_byte<char>
 133 {
 134 public:
 135    typedef _narrow_type width_type;
 136 };
 137
 138 template<>
 139 class is_byte<unsigned char>
 140 {
 141 public:
 142    typedef _narrow_type width_type;
 143 };
 144
 145 template<>
 146 class is_byte<signed char>
 147 {
 148 public:
 149    typedef _narrow_type width_type;
 150 };
 151
 152 template <class charT>
 153 class is_byte
 154 {
 155 public:
 156    typedef _wide_type width_type;
 157 };
 158
 159
 160 //
 161 // compiled structures
 162 //
 163 // the following defs describe the format of the compiled string
 164 //
 165
 166 //
 167 // enum syntax_element_type
 168 // describes the type of a record
 169 enum syntax_element_type
 170 {
 171    syntax_element_startmark = 0,
 172    syntax_element_endmark = syntax_element_startmark + 1,
 173    syntax_element_literal = syntax_element_endmark + 1,
 174    syntax_element_start_line = syntax_element_literal + 1,
 175    syntax_element_end_line = syntax_element_start_line + 1,
 176    syntax_element_wild = syntax_element_end_line + 1,
 177    syntax_element_match = syntax_element_wild + 1,
 178    syntax_element_word_boundary = syntax_element_match + 1,
 179    syntax_element_within_word = syntax_element_word_boundary + 1,
 180    syntax_element_word_start = syntax_element_within_word + 1,
 181    syntax_element_word_end = syntax_element_word_start + 1,
 182    syntax_element_buffer_start = syntax_element_word_end + 1,
 183    syntax_element_buffer_end = syntax_element_buffer_start + 1,
 184    syntax_element_backref = syntax_element_buffer_end + 1,
 185    syntax_element_long_set = syntax_element_backref + 1,
 186    syntax_element_set = syntax_element_long_set + 1,
 187    syntax_element_jump = syntax_element_set + 1,
 188    syntax_element_alt = syntax_element_jump + 1,
 189    syntax_element_rep = syntax_element_alt + 1,
 190    syntax_element_combining = syntax_element_rep + 1,
 191    syntax_element_soft_buffer_end = syntax_element_combining + 1,
 192    syntax_element_restart_continue = syntax_element_soft_buffer_end + 1
 193 };
 194
 195 #ifdef BOOST_REGEX_DEBUG
 196 // dwa 09/26/00 - This is needed to suppress warnings about an ambiguous conversion
 197 std::ostream& operator<<(std::ostream&, syntax_element_type);
 198 #endif
 199
 200 union offset_type
 201 {
 202    re_syntax_base* p;
 203    std::size_t i;
 204 };
 205
 206 //
 207 // struct re_syntax_base
 208 // base class for all syntax types:
 209 struct re_syntax_base
 210 {
 211    syntax_element_type type;
 212    offset_type next;
 213    unsigned int can_be_null;
 214 };
 215
 216 //
 217 // struct re_brace
 218 // marks start or end of (...)
 219 struct re_brace : public re_syntax_base
 220 {
 221    int index;
 222 };
 223
 224 //
 225 // struct re_literal
 226 // marks a literal string and
 227 // is followed by an array of charT[length]:
 228 struct re_literal : public re_syntax_base
 229 {
 230    unsigned int length;
 231 };
 232
 233 //
 234 // struct re_long_set
 235 // provides data for sets [...] containing
 236 // wide characters
 237 struct re_set_long : public re_syntax_base
 238 {
 239    unsigned int csingles, cranges, cequivalents;
 240    boost::uint_fast32_t cclasses;
 241    bool isnot;
 242 };
 243
 244 //
 245 // struct re_set
 246 // provides a map of bools for sets containing
 247 // narrow, single byte characters.
 248 struct re_set : public re_syntax_base
 249 {
 250    unsigned char _map[256];
 251 };
 252
 253 //
 254 // struct re_jump
 255 // provides alternative next destination
 256 struct re_jump : public re_syntax_base
 257 {
 258    offset_type alt;
 259    unsigned char _map[256];
 260 };
 261
 262 //
 263 // struct re_repeat
 264 // provides repeat expressions
 265 struct re_repeat : public re_jump
 266 {
 267    unsigned min, max;
 268    int id;
 269    bool leading;
 270    bool greedy;
 271 };
 272
 273
 274 //
 275 // enum re_jump_size_type
 276 // provides compiled size of re_jump
 277 // allowing for trailing alignment
 278 // provide this so we know how many
 279 // bytes to insert
 280 enum re_jump_size_type
 281 {
 282    re_jump_size = (sizeof(re_jump) + padding_mask) & ~(padding_mask),
 283    re_repeater_size = (sizeof(re_repeat) + padding_mask) & ~(padding_mask)
 284 };
 285
 286 } // namespace re_detail
 287
 288 //
 289 // class basic_regex
 290 // handles error codes and flags
 291
 292 class BOOST_REGEX_DECL regbase
 293 {
 294 public:
 295    enum flag_type_
 296    {
 297       escape_in_lists = 1,                     // '\' special inside [...]
 298       char_classes = escape_in_lists << 1,     // [[:CLASS:]] allowed
 299       intervals = char_classes << 1,           // {x,y} allowed
 300       limited_ops = intervals << 1,            // all of + ? and | are normal characters
 301       newline_alt = limited_ops << 1,          // \n is the same as |
 302       bk_plus_qm = newline_alt << 1,           // uses \+ and \?
 303       bk_braces = bk_plus_qm << 1,             // uses \{ and \}
 304       bk_parens = bk_braces << 1,              // uses \( and \)
 305       bk_refs = bk_parens << 1,                // \d allowed
 306       bk_vbar = bk_refs << 1,                  // uses \|
 307
 308       use_except = bk_vbar << 1,               // exception on error
 309       failbit = use_except << 1,               // error flag
 310       literal = failbit << 1,                  // all characters are literals
 311       icase = literal << 1,                    // characters are matched regardless of case
 312       nocollate = icase << 1,                  // don't use locale specific collation
 313
 314       basic = char_classes | intervals | limited_ops | bk_braces | bk_parens | bk_refs,
 315       extended = char_classes | intervals | bk_refs,
 316       normal = escape_in_lists | char_classes | intervals | bk_refs | nocollate,
 317       emacs = bk_braces | bk_parens | bk_refs | bk_vbar,
 318       awk = extended | escape_in_lists,
 319       grep = basic | newline_alt,
 320       egrep = extended | newline_alt,
 321       sed = basic,
 322       perl = normal
 323    };
 324    typedef unsigned int flag_type;
 325
 326    enum restart_info
 327    {
 328       restart_any = 0,
 329       restart_word = 1,
 330       restart_line = 2,
 331       restart_buf = 3,
 332       restart_continue = 4,
 333       restart_lit = 5,
 334       restart_fixed_lit = 6
 335    };
 336
 337    flag_type BOOST_REGEX_CALL flags()const
 338    {
 339       return _flags;
 340    }
 341
 342    regbase();
 343    regbase(const regbase& b);
 344 protected:
 345    flag_type _flags;
 346 };
 347
 348 //
 349 // some forward declarations:
 350 namespace re_detail{
 351 template <class iterator, class Allocator>
 352 class _priv_match_data;
 353
 354 #if defined(BOOST_NO_STD_ITERATOR_TRAITS) || defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 355
 356 template <class T>
 357 struct regex_iterator_traits
 358 {
 359   typedef typename T::iterator_category iterator_category;
 360   typedef typename T::value_type        value_type;
 361 #if !defined(BOOST_NO_STD_ITERATOR)
 362   typedef typename T::difference_type   difference_type;
 363   typedef typename T::pointer           pointer;
 364   typedef typename T::reference         reference;
 365 #else
 366   typedef std::ptrdiff_t                difference_type;
 367   typedef value_type*                   pointer;
 368   typedef value_type&                   reference;
 369 #endif
 370 };
 371
 372 template <class T>
 373 struct pointer_iterator_traits
 374 {
 375    typedef std::ptrdiff_t difference_type;
 376    typedef T value_type;
 377    typedef T* pointer;
 378    typedef T& reference;
 379    typedef std::random_access_iterator_tag iterator_category;
 380 };
 381 template <class T>
 382 struct const_pointer_iterator_traits
 383 {
 384    typedef std::ptrdiff_t difference_type;
 385    typedef T value_type;
 386    typedef const T* pointer;
 387    typedef const T& reference;
 388    typedef std::random_access_iterator_tag iterator_category;
 389 };
 390
 391 template<>
 392 struct regex_iterator_traits<char*> : pointer_iterator_traits<char>{};
 393 template<>
 394 struct regex_iterator_traits<const char*> : const_pointer_iterator_traits<char>{};
 395 template<>
 396 struct regex_iterator_traits<wchar_t*> : pointer_iterator_traits<wchar_t>{};
 397 template<>
 398 struct regex_iterator_traits<const wchar_t*> : const_pointer_iterator_traits<wchar_t>{};
 399
 400 #if defined(__SGI_STL_PORT) && defined(__STL_DEBUG)
 401 template<>
 402 struct regex_iterator_traits<std::string::iterator> : pointer_iterator_traits<char>{};
 403 template<>
 404 struct regex_iterator_traits<std::string::const_iterator> : const_pointer_iterator_traits<char>{};
 405 #ifndef BOOST_NO_STD_WSTRING
 406 template<>
 407 struct regex_iterator_traits<std::wstring::iterator> : pointer_iterator_traits<wchar_t>{};
 408 template<>
 409 struct regex_iterator_traits<std::wstring::const_iterator> : const_pointer_iterator_traits<wchar_t>{};
 410 #endif // BOOST_NO_WSTRING
 411 #endif // stport
 412
 413 #else
 414
 415 template <class T>
 416 struct regex_iterator_traits : public std::iterator_traits<T> {};
 417
 418 #endif
 419
 420 template <class I>
 421 struct def_alloc_param_traits
 422 {
 423    typedef typename regex_iterator_traits<I>::value_type const_value_type;
 424    typedef typename remove_cv<const_value_type>::type type;
 425 };
 426 template <>
 427 struct def_alloc_param_traits<const char*>
 428 {
 429    typedef char type;
 430 };
 431 template <>
 432 struct def_alloc_param_traits<const wchar_t*>
 433 {
 434    typedef wchar_t type;
 435 };
 436
 437 }
 438
 439 template <class iterator, class Allocator =
 440 #if !(defined(BOOST_MSVC) && (BOOST_MSVC <= 1300))
 441 BOOST_DEFAULT_ALLOCATOR(typename re_detail::def_alloc_param_traits<iterator>::type) >
 442 #else
 443 BOOST_DEFAULT_ALLOCATOR(re_detail::def_alloc_param_traits<iterator>::type) >
 444 #endif
 445 class match_results;
 446
 447 //
 448 // class reg_expression
 449 // represents the compiled
 450 // regular expression:
 451 //
 452
 453 #ifdef BOOST_REGEX_NO_FWD
 454 template <class charT, class traits = regex_traits<charT>, class Allocator = BOOST_DEFAULT_ALLOCATOR(charT) >
 455 #else
 456 template <class charT, class traits, class Allocator >
 457 #endif
 458 class reg_expression : public regbase
 459 {
 460 public:
 461    typedef typename traits::size_type traits_size_type;
 462    typedef typename traits::uchar_type traits_uchar_type;
 463    typedef typename traits::string_type traits_string_type;
 464    // typedefs:
 465    typedef charT char_type;
 466    typedef traits traits_type;
 467
 468    // locale_type
 469    // placeholder for actual locale type used by the
 470    // traits class to localise *this.
 471    typedef typename traits::locale_type locale_type;
 472    // value_type
 473    typedef charT value_type;
 474    // reference, const_reference
 475    typedef charT& reference;
 476    typedef const charT& const_reference;
 477    // iterator, const_iterator
 478    typedef const charT* const_iterator;
 479    typedef const_iterator iterator;
 480    // difference_type
 481    typedef typename Allocator::difference_type difference_type;
 482    // size_type
 483    typedef typename Allocator::size_type size_type;
 484    // allocator_type
 485    typedef Allocator allocator_type;
 486    typedef Allocator alloc_type;
 487    // flag_type
 488    typedef regbase::flag_type flag_type;
 489
 490 public:
 491    explicit reg_expression(const Allocator& a = Allocator());
 492    explicit reg_expression(const charT* p, flag_type f = regbase::normal, const Allocator& a = Allocator());
 493    reg_expression(const charT* p1, const charT* p2, flag_type f = regbase::normal, const Allocator& a = Allocator());
 494    reg_expression(const charT* p, size_type len, flag_type f, const Allocator& a = Allocator());
 495    reg_expression(const reg_expression&);
 496    ~reg_expression();
 497    reg_expression& BOOST_REGEX_CALL operator=(const reg_expression&);
 498    reg_expression& BOOST_REGEX_CALL operator=(const charT* ptr)
 499    {
 500       set_expression(ptr, regbase::normal | regbase::use_except);
 501       return *this;
 502    }
 503
 504    //
 505    // assign:
 506    reg_expression& assign(const reg_expression& that)
 507    { return *this = that; }
 508    reg_expression& assign(const charT* ptr, flag_type f = regbase::normal)
 509    {
 510       set_expression(ptr, f | regbase::use_except);
 511       return *this;
 512    }
 513
 514    reg_expression& assign(const charT* first,
 515                           const charT* last,
 516                           flag_type f = regbase::normal)
 517    {
 518       set_expression(first, last, f | regbase::use_except);
 519       return *this;
 520    }
 521 #ifndef BOOST_NO_MEMBER_TEMPLATES
 522
 523    template <class ST, class SA>
 524    unsigned int BOOST_REGEX_CALL set_expression(const std::basic_string<charT, ST, SA>& p, flag_type f = regbase::normal)
 525    { return set_expression(p.data(), p.data() + p.size(), f); }
 526
 527    template <class ST, class SA>
 528    explicit reg_expression(const std::basic_string<charT, ST, SA>& p, flag_type f = regbase::normal, const Allocator& a = Allocator())
 529     : data(a), pkmp(0), error_code_(REG_EMPTY), _expression(0) { set_expression(p, f | regbase::use_except); }
 530
 531    template <class I>
 532    reg_expression(I first, I last, flag_type f = regbase::normal, const Allocator& al = Allocator())
 533     : data(al), pkmp(0), error_code_(REG_EMPTY), _expression(0)
 534    {
 535       size_type len = last-first;
 536       scoped_array<charT> a(new charT[len]);
 537       std::copy(first, last, a.get());
 538       set_expression(a.get(), a.get() + len, f | regbase::use_except);
 539    }
 540
 541    template <class ST, class SA>
 542    reg_expression& BOOST_REGEX_CALL operator=(const std::basic_string<charT, ST, SA>& p)
 543    {
 544       set_expression(p.c_str(), p.c_str() + p.size(), regbase::normal | regbase::use_except);
 545       return *this;
 546    }
 547
 548    template <class string_traits, class A>
 549    reg_expression& BOOST_REGEX_CALL assign(
 550        const std::basic_string<charT, string_traits, A>& s,
 551        flag_type f = regbase::normal)
 552    {
 553       set_expression(s.c_str(), s.c_str() + s.size(), f | regbase::use_except);
 554       return *this;
 555    }
 556
 557    template <class fwd_iterator>
 558    reg_expression& BOOST_REGEX_CALL assign(fwd_iterator first,
 559                           fwd_iterator last,
 560                           flag_type f = regbase::normal)
 561    {
 562       size_type len = last-first;
 563       scoped_array<charT> a(new charT[len]);
 564       std::copy(first, last, a.get());
 565       set_expression(a.get(), a.get() + len, f | regbase::use_except);
 566       return *this;
 567    }
 568 #else
 569    unsigned int BOOST_REGEX_CALL set_expression(const std::basic_string<charT>& p, flag_type f = regbase::normal)
 570    { return set_expression(p.data(), p.data() + p.size(), f | regbase::use_except); }
 571
 572    reg_expression(const std::basic_string<charT>& p, flag_type f = regbase::normal, const Allocator& a = Allocator())
 573     : data(a), pkmp(0) { set_expression(p, f | regbase::use_except); }
 574
 575    reg_expression& BOOST_REGEX_CALL operator=(const std::basic_string<charT>& p)
 576    {
 577       set_expression(p.c_str(), p.c_str() + p.size(), regbase::normal | regbase::use_except);
 578       return *this;
 579    }
 580
 581    reg_expression& BOOST_REGEX_CALL assign(
 582        const std::basic_string<charT>& s,
 583        flag_type f = regbase::normal)
 584    {
 585       set_expression(s.c_str(), s.c_str() + s.size(), f | regbase::use_except);
 586       return *this;
 587    }
 588
 589 #endif
 590
 591
 592    //
 593    // allocator access:
 594    Allocator BOOST_REGEX_CALL get_allocator()const;
 595    //
 596    // locale:
 597    locale_type BOOST_REGEX_CALL imbue(locale_type l){ return traits_inst.imbue(l); }
 598    locale_type BOOST_REGEX_CALL getloc()const{ return traits_inst.getloc(); }
 599    //
 600    // flags:
 601    flag_type BOOST_REGEX_CALL getflags()const
 602    { return flags(); }
 603    //
 604    // str:
 605    std::basic_string<charT> BOOST_REGEX_CALL str()const
 606    {
 607       std::basic_string<charT> result;
 608       if(this->error_code() == 0)
 609          result = std::basic_string<charT>(_expression, _expression_len);
 610       return result;
 611    }
 612    //
 613    // begin, end:
 614    const_iterator BOOST_REGEX_CALL begin()const
 615    { return (this->error_code() ? 0 : _expression); }
 616    const_iterator BOOST_REGEX_CALL end()const
 617    { return (this->error_code() ? 0 : _expression + _expression_len); }
 618    //
 619    // swap:
 620    void BOOST_REGEX_CALL swap(reg_expression&)throw();
 621    //
 622    // size:
 623    size_type BOOST_REGEX_CALL size()const
 624    { return (this->error_code() ? 0 : _expression_len); }
 625    //
 626    // max_size:
 627    size_type BOOST_REGEX_CALL max_size()const
 628    { return UINT_MAX; }
 629    //
 630    // empty:
 631    bool BOOST_REGEX_CALL empty()const
 632    { return 0 != this->error_code(); }
 633
 634    unsigned BOOST_REGEX_CALL mark_count()const { return (this->error_code() ? 0 : marks); }
 635    bool BOOST_REGEX_CALL operator==(const reg_expression&)const;
 636    bool BOOST_REGEX_CALL operator<(const reg_expression&)const;
 637    //
 638    // The following are deprecated as public interfaces
 639    // but are available for compatibility with earlier versions.
 640    allocator_type BOOST_REGEX_CALL allocator()const;
 641    const charT* BOOST_REGEX_CALL expression()const { return (this->error_code() ? 0 : _expression); }
 642    unsigned int BOOST_REGEX_CALL set_expression(const charT* p, const charT* end, flag_type f = regbase::normal);
 643    unsigned int BOOST_REGEX_CALL set_expression(const charT* p, flag_type f = regbase::normal) { return set_expression(p, p + traits_type::length(p), f); }
 644    //
 645    // this should be private but template friends don't work:
 646    const traits_type& get_traits()const { return traits_inst; }
 647    unsigned int BOOST_REGEX_CALL error_code()const
 648    {
 649       return error_code_;
 650    }
 651
 652 private:
 653    traits_type traits_inst;
 654    re_detail::raw_storage<Allocator> data;
 655    unsigned _restart_type;
 656    unsigned marks;
 657    int repeats;
 658    unsigned char* startmap;
 659    std::size_t _expression_len;
 660    std::size_t _leading_len;
 661    const charT* _leading_string;
 662    std::size_t _leading_string_len;
 663    re_detail::kmp_info<charT>* pkmp;
 664    unsigned error_code_;
 665    charT* _expression;
 666
 667    void BOOST_REGEX_CALL compile_maps();
 668    void BOOST_REGEX_CALL compile_map(re_detail::re_syntax_base* node, unsigned char* _map, unsigned int* pnull, unsigned char mask, re_detail::re_syntax_base* terminal = 0)const;
 669    bool BOOST_REGEX_CALL probe_start(re_detail::re_syntax_base* node, charT c, re_detail::re_syntax_base* terminal)const;
 670    bool BOOST_REGEX_CALL probe_start_null(re_detail::re_syntax_base* node, re_detail::re_syntax_base* terminal)const;
 671    void BOOST_REGEX_CALL fixup_apply(re_detail::re_syntax_base* b, unsigned cbraces);
 672    void BOOST_REGEX_CALL move_offsets(re_detail::re_syntax_base* j, unsigned size);
 673    re_detail::re_syntax_base* BOOST_REGEX_CALL compile_set(const charT*& first, const charT* last);
 674    re_detail::re_syntax_base* BOOST_REGEX_CALL 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&);
 675    re_detail::re_syntax_base* BOOST_REGEX_CALL 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&);
 676    re_detail::re_syntax_base* BOOST_REGEX_CALL compile_set_simple(re_detail::re_syntax_base* dat, unsigned long cls, bool isnot = false);
 677    unsigned int BOOST_REGEX_CALL parse_inner_set(const charT*& first, const charT* last);
 678
 679    re_detail::re_syntax_base* BOOST_REGEX_CALL add_simple(re_detail::re_syntax_base* dat, re_detail::syntax_element_type type, unsigned int size = sizeof(re_detail::re_syntax_base));
 680    re_detail::re_syntax_base* BOOST_REGEX_CALL add_literal(re_detail::re_syntax_base* dat, charT c);
 681    charT BOOST_REGEX_CALL parse_escape(const charT*& first, const charT* last);
 682    void BOOST_REGEX_CALL parse_range(const charT*& first, const charT* last, unsigned& min, unsigned& max);
 683    bool BOOST_REGEX_CALL skip_space(const charT*& first, const charT* last);
 684    unsigned int BOOST_REGEX_CALL probe_restart(re_detail::re_syntax_base* dat);
 685    unsigned int BOOST_REGEX_CALL fixup_leading_rep(re_detail::re_syntax_base* dat, re_detail::re_syntax_base* end);
 686    void BOOST_REGEX_CALL fail(unsigned int err);
 687
 688 protected:
 689    static int BOOST_REGEX_CALL repeat_count(const reg_expression& e)
 690    { return e.repeats; }
 691    static unsigned int BOOST_REGEX_CALL restart_type(const reg_expression& e)
 692    { return e._restart_type; }
 693    static const re_detail::re_syntax_base* BOOST_REGEX_CALL first(const reg_expression& e)
 694    { return (const re_detail::re_syntax_base*)e.data.data(); }
 695    static const unsigned char* BOOST_REGEX_CALL get_map(const reg_expression& e)
 696    { return e.startmap; }
 697    static std::size_t BOOST_REGEX_CALL leading_length(const reg_expression& e)
 698    { return e._leading_len; }
 699    static const re_detail::kmp_info<charT>* get_kmp(const reg_expression& e)
 700    { return e.pkmp; }
 701    static bool BOOST_REGEX_CALL can_start(charT c, const unsigned char* _map, unsigned char mask, const re_detail::_wide_type&);
 702    static bool BOOST_REGEX_CALL can_start(charT c, const unsigned char* _map, unsigned char mask, const re_detail::_narrow_type&);
 703 };
 704
 705 template <class charT, class traits, class Allocator>
 706 inline void BOOST_REGEX_CALL reg_expression<charT, traits, Allocator>::swap(reg_expression& that)throw()
 707 {
 708    // this is not as efficient as it should be,
 709    // however swapping traits classes is problematic
 710    // so just use 'brute force' method for now:
 711    reg_expression<charT, traits, Allocator> e(that);
 712    that = *this;
 713    *this = e;
 714 }
 715
 716
 717 //
 718 // class match_results and match_results_base
 719 // handles what matched where
 720
 721 template <class iterator>
 722 struct sub_match
 723 {
 724    typedef typename re_detail::regex_iterator_traits<iterator>::value_type       value_type;
 725 #if defined(BOOST_NO_STD_ITERATOR_TRAITS) || defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 726    typedef std::ptrdiff_t  difference_type;
 727 #else
 728    typedef typename re_detail::regex_iterator_traits<iterator>::difference_type       difference_type;
 729 #endif
 730    typedef iterator                                                  iterator_type;
 731
 732    iterator first;
 733    iterator second;
 734    bool matched;
 735
 736    operator std::basic_string<value_type> ()const
 737    {
 738       std::basic_string<value_type> result;
 739       std::size_t len = boost::re_detail::distance((iterator)first, (iterator)second);
 740       result.reserve(len);
 741       iterator i = first;
 742       while(i != second)
 743       {
 744          result.append(1, *i);
 745          ++i;
 746       }
 747       return result;
 748    }
 749    #ifdef BOOST_OLD_REGEX_H
 750    //
 751    // the following are deprecated, do not use!!
 752    //
 753    operator int()const;
 754    operator unsigned int()const;
 755    operator short()const
 756    {
 757       return (short)(int)(*this);
 758    }
 759    operator unsigned short()const
 760    {
 761       return (unsigned short)(unsigned int)(*this);
 762    }
 763    #endif
 764    sub_match() { matched = false; }
 765    sub_match(iterator i) : first(i), second(i), matched(false) {}
 766
 767    bool operator==(const sub_match& that)const
 768    {
 769       return (first == that.first) && (second == that.second) && (matched == that.matched);
 770    }
 771    bool BOOST_REGEX_CALL operator !=(const sub_match& that)const
 772    { return !(*this == that); }
 773
 774    difference_type BOOST_REGEX_CALL length()const
 775    {
 776       difference_type n = boost::re_detail::distance((iterator)first, (iterator)second);
 777       return n;
 778    }
 779 };
 780
 781 #ifdef BOOST_OLD_REGEX_H
 782 namespace re_detail{
 783 template <class iterator, class charT>
 784 int do_toi(iterator i, iterator j, char c, int radix)
 785 {
 786    std::string s(i, j);
 787    char* p;
 788    int result = std::strtol(s.c_str(), &p, radix);
 789 #ifndef BOOST_NO_EXCEPTIONS
 790    if(*p)throw bad_pattern("Bad sub-expression");
 791 #endif
 792    BOOST_REGEX_NOEH_ASSERT(0 == *p)
 793    return result;
 794 }
 795
 796 //
 797 // helper:
 798 template <class I, class charT>
 799 int do_toi(I& i, I j, charT c)
 800 {
 801    int result = 0;
 802    while((i != j) && (isdigit(*i)))
 803    {
 804       result = result*10 + (*i - '0');
 805       ++i;
 806    }
 807    return result;
 808 }
 809 }
 810
 811
 812 template <class iterator>
 813 sub_match<iterator>::operator int()const
 814 {
 815    iterator i = first;
 816    iterator j = second;
 817 #ifndef BOOST_NO_EXCEPTIONS
 818    if(i == j)throw bad_pattern("Bad sub-expression");
 819 #endif
 820    BOOST_REGEX_NOEH_ASSERT(i != j)
 821    int neg = 1;
 822    if((i != j) && (*i == '-'))
 823    {
 824       neg = -1;
 825       ++i;
 826    }
 827    neg *= re_detail::do_toi(i, j, *i);
 828 #ifndef BOOST_NO_EXCEPTIONS
 829    if(i != j)throw bad_pattern("Bad sub-expression");
 830 #endif
 831    BOOST_REGEX_NOEH_ASSERT(i == j)
 832    return neg;
 833 }
 834 template <class iterator>
 835 sub_match<iterator>::operator unsigned int()const
 836 {
 837    iterator i = first;
 838    iterator j = second;
 839 #ifndef BOOST_NO_EXCEPTIONS
 840    if(i == j)
 841       throw bad_pattern("Bad sub-expression");
 842 #endif
 843    BOOST_REGEX_NOEH_ASSERT(i != j)
 844    return re_detail::do_toi(i, j, *first);
 845 }
 846 #endif
 847
 848 namespace re_detail{
 849
 850 template <class iterator, class Allocator = BOOST_DEFAULT_ALLOCATOR(typename def_alloc_param_traits<iterator>::type) >
 851 class match_results_base
 852 {
 853 public:
 854    typedef Allocator                                                 alloc_type;
 855    typedef typename boost::detail::rebind_allocator<iterator, Allocator>::type  iterator_alloc;
 856    typedef typename iterator_alloc::size_type                        size_type;
 857 #if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_NO_STD_ITERATOR_TRAITS)
 858    typedef typename std::iterator_traits<iterator>::difference_type  difference_type;
 859    typedef typename std::iterator_traits<iterator>::value_type       char_type;
 860 #else
 861    typedef std::ptrdiff_t                                            difference_type;
 862    typedef typename re_detail::regex_iterator_traits<iterator>::value_type char_type;
 863 #endif
 864    typedef sub_match<iterator>                                       value_type;
 865    typedef iterator                                                  iterator_type;
 866
 867 protected:
 868    typedef typename boost::detail::rebind_allocator<char, Allocator>::type c_alloc;
 869
 870    struct c_reference : public c_alloc
 871    {
 872       std::size_t cmatches;
 873       unsigned count;
 874       sub_match<iterator> head, tail, null;
 875       unsigned int lines;
 876       iterator line_pos, base;
 877       c_reference(const Allocator& a)
 878          : c_alloc(a), cmatches(0), count(0), lines(0) {  }
 879
 880       bool operator==(const c_reference& that)const
 881       {
 882          return (cmatches == that.cmatches) &&
 883                   (count == that.count) &&
 884                   (head == that.head) &&
 885                   (tail == that.tail) &&
 886                   (lines == that.lines) &&
 887                   (base == that.base);
 888       }
 889       bool operator!=(const c_reference& that)const
 890       { return !(*this == that); }
 891    };
 892
 893    c_reference* ref;
 894
 895    void BOOST_REGEX_CALL cow();
 896
 897    // protected contructor for derived class...
 898    match_results_base(bool){}
 899    void BOOST_REGEX_CALL m_free();
 900
 901 public:
 902
 903    match_results_base(const Allocator& a = Allocator());
 904
 905    match_results_base(const match_results_base& m)
 906    {
 907       ref = m.ref;
 908       ++(ref->count);
 909    }
 910
 911    match_results_base& BOOST_REGEX_CALL operator=(const match_results_base& m);
 912
 913    ~match_results_base()
 914    {
 915       m_free();
 916    }
 917
 918    size_type BOOST_REGEX_CALL size()const
 919    {
 920       //return (*this)[0].matched ? ref->cmatches : 0;
 921       return ref->cmatches;
 922    }
 923
 924    const sub_match<iterator>& BOOST_REGEX_CALL operator[](int n) const
 925    {
 926       if((n >= 0) && ((unsigned int)n < ref->cmatches))
 927          return *(sub_match<iterator>*)((char*)ref + sizeof(c_reference) + sizeof(sub_match<iterator>)*n);
 928       return (n == -1) ? ref->head : (n == -2) ? ref->tail : ref->null;
 929    }
 930
 931    Allocator BOOST_REGEX_CALL allocator()const;
 932
 933    difference_type BOOST_REGEX_CALL length(unsigned int sub = 0)const
 934    {
 935       jm_assert(ref->cmatches);
 936       const sub_match<iterator>& m = (*this)[sub];
 937       if(m.matched == false)
 938          return 0;
 939       difference_type n = boost::re_detail::distance((iterator)m.first, (iterator)m.second);
 940       return n;
 941    }
 942
 943    std::basic_string<char_type> str(int i)const
 944    {
 945       return static_cast<std::basic_string<char_type> >((*this)[i]);
 946    }
 947
 948    unsigned int BOOST_REGEX_CALL line()const
 949    {
 950       return ref->lines;
 951    }
 952
 953    difference_type BOOST_REGEX_CALL position(unsigned int sub = 0)const
 954    {
 955       jm_assert(ref->cmatches);
 956       const sub_match<iterator>& s = (*this)[sub];
 957       if(s.matched == false)
 958          return -1;
 959       difference_type n = boost::re_detail::distance((iterator)(ref->base), (iterator)(s.first));
 960       return n;
 961    }
 962
 963    iterator BOOST_REGEX_CALL line_start()const
 964    {
 965       return ref->line_pos;
 966    }
 967
 968    void swap(match_results_base& that)
 969    {
 970       c_reference* t = that.ref;
 971       that.ref = ref;
 972       ref = t;
 973    }
 974
 975    bool operator==(const match_results_base& that)const;
 976    bool operator<(const match_results_base& that)const
 977    { return position() < that.position(); }
 978
 979    friend class match_results<iterator, Allocator>;
 980
 981    void BOOST_REGEX_CALL set_size(size_type n);
 982    void BOOST_REGEX_CALL set_size(size_type n, iterator i, iterator j);
 983    void BOOST_REGEX_CALL maybe_assign(const match_results_base& m);
 984    void BOOST_REGEX_CALL init_fail(iterator i, iterator j);
 985
 986    void BOOST_REGEX_CALL set_first(iterator i);
 987    void BOOST_REGEX_CALL set_first(iterator i, std::size_t pos);
 988
 989    void BOOST_REGEX_CALL set_second(iterator i)
 990    {
 991       cow();
 992       ((sub_match<iterator>*)(ref+1))->second = i;
 993       ((sub_match<iterator>*)(ref+1))->matched = true;
 994       ref->tail.first = i;
 995       ref->tail.matched = (ref->tail.first == ref->tail.second) ? false : true;
 996    }
 997
 998    void BOOST_REGEX_CALL set_second(iterator i, std::size_t pos, bool m = true)
 999    {
1000       cow();
1001       ((sub_match<iterator>*)((char*)ref + sizeof(c_reference) + sizeof(sub_match<iterator>) * pos))->second = i;
1002       ((sub_match<iterator>*)((char*)ref + sizeof(c_reference) + sizeof(sub_match<iterator>) * pos))->matched = m;
1003       if(pos == 0)
1004       {
1005          ref->tail.first = i;
1006          ref->tail.matched = (ref->tail.first == ref->tail.second) ? false : true;
1007       }
1008    }
1009
1010    void BOOST_REGEX_CALL set_line(unsigned int i, iterator pos)
1011    {
1012       ref->lines = i;
1013       ref->line_pos = pos;
1014    }
1015
1016    void BOOST_REGEX_CALL set_base(iterator pos)
1017    {
1018       ref->base = pos;
1019    }
1020 };
1021
1022 template <class iterator, class Allocator>
1023 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::set_first(iterator i)
1024 {
1025    cow();
1026    ref->head.second = i;
1027    ref->head.matched = (ref->head.first == ref->head.second) ? false : true;
1028    sub_match<iterator>* p1 = (sub_match<iterator>*)(ref+1);
1029    sub_match<iterator>* p2 = p1 + ref->cmatches;
1030    p1->first = i;
1031    p1->matched = false;
1032    ++p1;
1033    while(p1 != p2)
1034    {
1035       p1->matched = false;
1036       p1->first = ref->tail.second;
1037       p1->second = ref->tail.second;
1038       ++p1;
1039    }
1040 }
1041
1042 template <class iterator, class Allocator>
1043 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::set_first(iterator i, std::size_t pos)
1044 {
1045    cow();
1046    ((sub_match<iterator>*)((char*)ref + sizeof(c_reference) + sizeof(sub_match<iterator>) * pos))->first = i;
1047    if(pos == 0)
1048    {
1049       ref->head.second = i;
1050       ref->head.matched = (ref->head.first == ref->head.second) ? false : true;
1051       sub_match<iterator>* p1 = (sub_match<iterator>*)(ref+1);
1052       sub_match<iterator>* p2 = p1 + ref->cmatches;
1053       p1->first = i;
1054       p1->matched = false;
1055       ++p1;
1056       while(p1 != p2)
1057       {
1058          p1->matched = false;
1059          p1->first = ref->tail.second;
1060          p1->second = ref->tail.second;
1061          ++p1;
1062       }
1063    }
1064 }
1065
1066
1067 template <class iterator, class Allocator>
1068 match_results_base<iterator, Allocator>::match_results_base(const Allocator& a)
1069 {
1070    ref = (c_reference*)c_alloc(a).allocate(sizeof(sub_match<iterator>) + sizeof(c_reference));
1071    BOOST_REGEX_NOEH_ASSERT(ref)
1072 #ifndef BOOST_NO_EXCEPTIONS
1073    try
1074    {
1075 #endif
1076       new (ref) c_reference(a);
1077       ref->cmatches = 1;
1078       ref->count = 1;
1079       // construct the sub_match<iterator>:
1080 #ifndef BOOST_NO_EXCEPTIONS
1081       try
1082       {
1083 #endif
1084          new ((sub_match<iterator>*)(ref+1)) sub_match<iterator>();
1085 #ifndef BOOST_NO_EXCEPTIONS
1086       }
1087       catch(...)
1088       {
1089          ::boost::re_detail::pointer_destroy(ref);
1090          throw;
1091       }
1092    }
1093    catch(...)
1094    {
1095       c_alloc(a).deallocate((char*)(void*)ref, sizeof(sub_match<iterator>) + sizeof(c_reference));
1096       throw;
1097    }
1098 #endif
1099 }
1100
1101 template <class iterator, class Allocator>
1102 Allocator BOOST_REGEX_CALL match_results_base<iterator, Allocator>::allocator()const
1103 {
1104   return *((c_alloc*)ref);
1105 }
1106
1107 template <class iterator, class Allocator>
1108 inline match_results_base<iterator, Allocator>& BOOST_REGEX_CALL match_results_base<iterator, Allocator>::operator=(const match_results_base<iterator, Allocator>& m)
1109 {
1110    if(ref != m.ref)
1111    {
1112       m_free();
1113       ref = m.ref;
1114       ++(ref->count);
1115    }
1116    return *this;
1117 }
1118
1119
1120 template <class iterator, class Allocator>
1121 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::m_free()
1122 {
1123    if(--(ref->count) == 0)
1124    {
1125       c_alloc a(*ref);
1126       sub_match<iterator>* p1, *p2;
1127       p1 = (sub_match<iterator>*)(ref+1);
1128       p2 = p1 + ref->cmatches;
1129       while(p1 != p2)
1130       {
1131          ::boost::re_detail::pointer_destroy(p1);
1132          ++p1;
1133       }
1134       ::boost::re_detail::pointer_destroy(ref);
1135       a.deallocate((char*)(void*)ref, sizeof(sub_match<iterator>) * ref->cmatches + sizeof(c_reference));
1136    }
1137 }
1138
1139 template <class iterator, class Allocator>
1140 bool match_results_base<iterator, Allocator>::operator==(const match_results_base<iterator, Allocator>& that)const
1141 {
1142    if(*ref != *(that.ref))
1143       return false;
1144    const sub_match<iterator>* p1 = (sub_match<iterator>*)(ref+1);
1145    const sub_match<iterator>* p2 = p1 + ref->cmatches;
1146    const sub_match<iterator>* p3 = (sub_match<iterator>*)(that.ref+1);
1147    while(p1 != p2)
1148    {
1149       if(*p1 != *p3)
1150          return false;
1151       ++p1;
1152       ++p3;
1153    }
1154    return true;
1155 }
1156
1157 template <class iterator, class Allocator>
1158 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::set_size(size_type n)
1159 {
1160    if(ref->cmatches != n)
1161    {
1162       c_reference* newref = (c_reference*)ref->allocate(sizeof(sub_match<iterator>) * n + sizeof(c_reference));
1163       BOOST_REGEX_NOEH_ASSERT(newref)
1164 #ifndef BOOST_NO_EXCEPTIONS
1165       try
1166       {
1167 #endif
1168          new (newref) c_reference(*ref);
1169          newref->count = 1;
1170          newref->cmatches = n;
1171          sub_match<iterator>* p1, *p2;
1172          p1 = (sub_match<iterator>*)(newref+1);
1173          p2 = p1 + newref->cmatches;
1174 #ifndef BOOST_NO_EXCEPTIONS
1175          try
1176          {
1177 #endif
1178             while(p1 != p2)
1179             {
1180                new (p1) sub_match<iterator>();
1181                ++p1;
1182             }
1183             m_free();
1184 #ifndef BOOST_NO_EXCEPTIONS
1185          }
1186          catch(...)
1187          {
1188             p2 = (sub_match<iterator>*)(newref+1);
1189             while(p2 != p1)
1190             {
1191                ::boost::re_detail::pointer_destroy(p2);
1192                ++p2;
1193             }
1194             ::boost::re_detail::pointer_destroy(ref);
1195             throw;
1196          }
1197 #endif
1198          ref = newref;
1199 #ifndef BOOST_NO_EXCEPTIONS
1200       }
1201       catch(...)
1202       {
1203          ref->deallocate((char*)(void*)newref, sizeof(sub_match<iterator>) * n + sizeof(c_reference));
1204          throw;
1205       }
1206 #endif
1207    }
1208 }
1209
1210 template <class iterator, class Allocator>
1211 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::set_size(size_type n, iterator i, iterator j)
1212 {
1213    if(ref->cmatches != n)
1214    {
1215       c_reference* newref = (c_reference*)ref->allocate(sizeof(sub_match<iterator>) * n + sizeof(c_reference));
1216       BOOST_REGEX_NOEH_ASSERT(newref)
1217 #ifndef BOOST_NO_EXCEPTIONS
1218       try{
1219 #endif
1220          new (newref) c_reference(*ref);
1221          newref->count = 1;
1222          newref->cmatches = n;
1223          sub_match<iterator>* p1 = (sub_match<iterator>*)(newref+1);
1224          sub_match<iterator>* p2 = p1 + newref->cmatches;
1225 #ifndef BOOST_NO_EXCEPTIONS
1226          try
1227          {
1228 #endif
1229             while(p1 != p2)
1230             {
1231                new (p1) sub_match<iterator>(j);
1232                ++p1;
1233             }
1234             m_free();
1235 #ifndef BOOST_NO_EXCEPTIONS
1236          }
1237          catch(...)
1238          {
1239             p2 = (sub_match<iterator>*)(newref+1);
1240             while(p2 != p1)
1241             {
1242                ::boost::re_detail::pointer_destroy(p2);
1243                ++p2;
1244             }
1245             ::boost::re_detail::pointer_destroy(ref);
1246             throw;
1247          }
1248 #endif
1249          ref = newref;
1250 #ifndef BOOST_NO_EXCEPTIONS
1251       }
1252       catch(...)
1253       {
1254          ref->deallocate((char*)(void*)newref, sizeof(sub_match<iterator>) * n + sizeof(c_reference));
1255          throw;
1256       }
1257 #endif
1258    }
1259    else
1260    {
1261       cow();
1262       // set iterators to be i, matched to false:
1263       sub_match<iterator>* p1, *p2;
1264       p1 = (sub_match<iterator>*)(ref+1);
1265       p2 = p1 + ref->cmatches;
1266       while(p1 != p2)
1267       {
1268          p1->first = j;
1269          p1->second = j;
1270          p1->matched = false;
1271          ++p1;
1272       }
1273    }
1274    ref->head.first = i;
1275    ref->tail.second = j;
1276    ref->head.matched = ref->tail.matched = true;
1277    ref->null.first = ref->null.second = j;
1278    ref->null.matched = false;
1279 }
1280
1281 template <class iterator, class Allocator>
1282 inline void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::init_fail(iterator i, iterator j)
1283 {
1284    set_size(ref->cmatches, i, j);
1285 }
1286
1287 template <class iterator, class Allocator>
1288 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::maybe_assign(const match_results_base<iterator, Allocator>& m)
1289 {
1290    sub_match<iterator>* p1, *p2;
1291    p1 = (sub_match<iterator>*)(ref+1);
1292    p2 = (sub_match<iterator>*)(m.ref+1);
1293    iterator base = (*this)[-1].first;
1294    std::size_t len1 = 0;
1295    std::size_t len2 = 0;
1296    std::size_t base1 = 0;
1297    std::size_t base2 = 0;
1298    std::size_t i;
1299    for(i = 0; i < ref->cmatches; ++i)
1300    {
1301       //
1302       // leftmost takes priority over longest:
1303       base1 = boost::re_detail::distance(base, p1->first);
1304       base2 = boost::re_detail::distance(base, p2->first);
1305       if(base1 < base2) return;
1306       if(base2 < base1) break;
1307
1308       len1 = boost::re_detail::distance(p1->first, p1->second);
1309       len2 = boost::re_detail::distance(p2->first, p2->second);
1310       if((len1 != len2) || ((p1->matched == false) && (p2->matched == true)))
1311          break;
1312       if((p1->matched == true) && (p2->matched == false))
1313          return;
1314       ++p1;
1315       ++p2;
1316    }
1317    if(i == ref->cmatches)
1318       return;
1319    if(base2 < base1)
1320       *this = m;
1321    else if((len2 > len1) || ((p1->matched == false) && (p2->matched == true)) )
1322       *this = m;
1323 }
1324
1325 template <class iterator, class Allocator>
1326 void BOOST_REGEX_CALL match_results_base<iterator, Allocator>::cow()
1327 {
1328    if(ref->count > 1)
1329    {
1330       c_reference* newref = (c_reference*)ref->allocate(sizeof(sub_match<iterator>) * ref->cmatches + sizeof(c_reference));
1331       BOOST_REGEX_NOEH_ASSERT(newref)
1332 #ifndef BOOST_NO_EXCEPTIONS
1333       try{
1334 #endif
1335          new (newref) c_reference(*ref);
1336          newref->count = 1;
1337          sub_match<iterator>* p1 = (sub_match<iterator>*)(newref+1);
1338          sub_match<iterator>* p2 = p1 + newref->cmatches;
1339          sub_match<iterator>* p3 = (sub_match<iterator>*)(ref+1);
1340 #ifndef BOOST_NO_EXCEPTIONS
1341          try{
1342 #endif
1343             while(p1 != p2)
1344             {
1345                new (p1) sub_match<iterator>(*p3);
1346                ++p1;
1347                ++p3;
1348             }
1349 #ifndef BOOST_NO_EXCEPTIONS
1350          }
1351          catch(...)
1352          {
1353             p2 = (sub_match<iterator>*)(newref+1);
1354             while(p2 != p1)
1355             {
1356                ::boost::re_detail::pointer_destroy(p2);
1357                ++p2;
1358             }
1359             ::boost::re_detail::pointer_destroy(ref);
1360             throw;
1361          }
1362 #endif
1363       --(ref->count);
1364       ref = newref;
1365 #ifndef BOOST_NO_EXCEPTIONS
1366       }
1367       catch(...)
1368       {
1369          ref->deallocate((char*)(void*)newref, sizeof(sub_match<iterator>) * ref->cmatches + sizeof(c_reference));
1370          throw;
1371       }
1372 #endif
1373    }
1374 }
1375
1376 } // namespace re_detail
1377
1378 //
1379 // class match_results
1380 // encapsulates match_results_base, does a deep copy rather than
1381 // reference counting to ensure thread safety when copying
1382 // other match_results instances
1383
1384 template <class iterator, class Allocator>
1385 class match_results : public re_detail::match_results_base<iterator, Allocator>
1386 {
1387    typedef re_detail::match_results_base<iterator, Allocator> base_type;
1388 public:
1389
1390    typedef typename base_type::alloc_type          alloc_type;
1391    typedef typename base_type::size_type           size_type;
1392    typedef typename base_type::char_type           char_type;
1393    typedef typename base_type::value_type          value_type;
1394    typedef typename base_type::difference_type     difference_type;
1395    typedef typename base_type::iterator_type       iterator_type;
1396
1397    explicit match_results(const Allocator& a = Allocator())
1398       : re_detail::match_results_base<iterator, Allocator>(a){}
1399
1400    match_results(const re_detail::match_results_base<iterator, Allocator>& m)
1401       : re_detail::match_results_base<iterator, Allocator>(m){}
1402
1403    match_results& operator=(const re_detail::match_results_base<iterator, Allocator>& m)
1404    {
1405       // shallow copy
1406       base_type::operator=(m);
1407       return *this;
1408    }
1409
1410    match_results(const match_results& m);
1411    match_results& operator=(const match_results& m);
1412    //
1413    // the following function definitions should *not* be required, except
1414    // when this class is used as a template inside another template definition,
1415    // in which members of the base class are not visible to the calling code.
1416    // As a workaround we define simple forwarding functions:
1417    //
1418    size_type size()const
1419    { return static_cast<const base_type*>(this)->size(); }
1420
1421    const sub_match<iterator>& operator[](int n) const
1422    { return (*static_cast<const base_type*>(this))[n]; }
1423
1424    Allocator allocator()const
1425    { return static_cast<const base_type*>(this)->allocator(); }
1426
1427    difference_type length(int sub = 0)const
1428    { return static_cast<const base_type*>(this)->length(sub); }
1429
1430    difference_type position(unsigned int sub = 0)const
1431    { return static_cast<const base_type*>(this)->position(sub); }
1432
1433    unsigned int line()const
1434    { return static_cast<const base_type*>(this)->line(); }
1435
1436    iterator line_start()const
1437    { return static_cast<const base_type*>(this)->line_start(); }
1438
1439    std::basic_string<char_type> str(int sub = 0)const
1440    { return static_cast<const base_type*>(this)->str(sub); }
1441
1442    void swap(match_results& that)
1443    { static_cast<base_type*>(this)->swap(that); }
1444
1445    bool operator==(const match_results& that)const
1446    { return static_cast<const base_type&>(*this) == static_cast<const base_type&>(that); }
1447
1448    bool operator<(const match_results& that) const
1449    { return position() < that.position(); }
1450 };
1451
1452 template <class iterator, class Allocator>
1453 match_results<iterator, Allocator>::match_results(const match_results<iterator, Allocator>& m)
1454    : re_detail::match_results_base<iterator, Allocator>(false)
1455 {
1456    this->ref =
1457       reinterpret_cast<typename re_detail::match_results_base<iterator, Allocator>::c_reference *>
1458          (m.ref->allocate(sizeof(sub_match<iterator>) * m.ref->cmatches +
1459                           sizeof(typename re_detail::match_results_base<iterator, Allocator>::c_reference)));
1460    BOOST_REGEX_NOEH_ASSERT(this->ref)
1461 #ifndef BOOST_NO_EXCEPTIONS
1462    try{
1463 #endif
1464       new (this->ref) typename re_detail::match_results_base<iterator, Allocator>::c_reference(*m.ref);
1465       this->ref->count = 1;
1466       sub_match<iterator>* p1 = (sub_match<iterator>*)(this->ref+1);
1467       sub_match<iterator>* p2 = p1 + this->ref->cmatches;
1468       sub_match<iterator>* p3 = (sub_match<iterator>*)(m.ref+1);
1469 #ifndef BOOST_NO_EXCEPTIONS
1470       try{
1471 #endif
1472          while(p1 != p2)
1473          {
1474             new (p1) sub_match<iterator>(*p3);
1475             ++p1;
1476             ++p3;
1477          }
1478 #ifndef BOOST_NO_EXCEPTIONS
1479       }
1480       catch(...)
1481       {
1482          p2 = (sub_match<iterator>*)(this->ref+1);
1483          while(p2 != p1)
1484          {
1485             re_detail::pointer_destroy(p2);
1486             ++p2;
1487          }
1488          re_detail::pointer_destroy(this->ref);
1489          throw;
1490       }
1491    }
1492    catch(...)
1493    {
1494       m.ref->deallocate((char*)(void*)this->ref, sizeof(sub_match<iterator>) * m.ref->cmatches + sizeof(typename re_detail::match_results_base<iterator, Allocator>::c_reference));
1495       throw;
1496    }
1497 #endif
1498 }
1499
1500 template <class iterator, class Allocator>
1501 match_results<iterator, Allocator>& match_results<iterator, Allocator>::operator=(const match_results<iterator, Allocator>& m)
1502 {
1503    match_results<iterator, Allocator> t(m);
1504    this->swap(t);
1505    return *this;
1506 }
1507
1508 namespace re_detail{
1509 template <class iterator, class charT, class traits_type, class Allocator>
1510 iterator BOOST_REGEX_CALL re_is_set_member(iterator next,
1511                           iterator last,
1512                           const re_set_long* set_,
1513                           const reg_expression<charT, traits_type, Allocator>& e);
1514 } // namepsace re_detail
1515
1516 #ifdef __BORLANDC__
1517   #pragma option pop
1518 #endif
1519
1520 } // namespace boost
1521
1522 #include <boost/regex/detail/regex_compile.hpp>
1523
1524 //
1525 // template instances:
1526 //
1527 #define BOOST_REGEX_CHAR_T char
1528 #ifdef BOOST_REGEX_NARROW_INSTANTIATE
1529 #  define BOOST_REGEX_INSTANTIATE
1530 #endif
1531 #include <boost/regex/detail/instances.hpp>
1532 #undef BOOST_REGEX_CHAR_T
1533 #ifdef BOOST_REGEX_INSTANTIATE
1534 #  undef BOOST_REGEX_INSTANTIATE
1535 #endif
1536
1537 #ifndef BOOST_NO_WREGEX
1538 #define BOOST_REGEX_CHAR_T wchar_t
1539 #ifdef BOOST_REGEX_WIDE_INSTANTIATE
1540 #  define BOOST_REGEX_INSTANTIATE
1541 #endif
1542 #include <boost/regex/detail/instances.hpp>
1543 #undef BOOST_REGEX_CHAR_T
1544 #ifdef BOOST_REGEX_INSTANTIATE
1545 #  undef BOOST_REGEX_INSTANTIATE
1546 #endif
1547 #endif
1548
1549
1550 namespace boost{
1551 #ifdef BOOST_REGEX_NO_FWD
1552 typedef reg_expression<char, regex_traits<char>, BOOST_DEFAULT_ALLOCATOR(char)> regex;
1553 #ifndef BOOST_NO_WREGEX
1554 typedef reg_expression<wchar_t, regex_traits<wchar_t>, BOOST_DEFAULT_ALLOCATOR(wchar_t)> wregex;
1555 #endif
1556 #endif
1557
1558 typedef match_results<const char*> cmatch;
1559 typedef match_results<std::string::const_iterator> smatch;
1560 #ifndef BOOST_NO_WREGEX
1561 typedef match_results<const wchar_t*> wcmatch;
1562 typedef match_results<std::wstring::const_iterator> wsmatch;
1563 #endif
1564
1565 } // namespace boost
1566 #include <boost/regex/detail/regex_match.hpp>
1567 #include <boost/regex/detail/regex_format.hpp>
1568 #include <boost/regex/detail/regex_split.hpp>
1569
1570
1571 #endif  // __cplusplus
1572
1573 #endif  // include
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600