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