boost/xpressive/regex_algorithms.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 /// \file regex_algorithms.hpp
   3 /// Contains the regex_match(), regex_search() and regex_replace() algorithms.
   4 //
   5 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   6 //  Software License, Version 1.0. (See accompanying file
   7 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_XPRESSIVE_ALGORITHMS_HPP_EAN_10_04_2005
  10 #define BOOST_XPRESSIVE_ALGORITHMS_HPP_EAN_10_04_2005
  11
  12 // MS compatible compilers support #pragma once
  13 #if defined(_MSC_VER) && (_MSC_VER >= 1020)
  14 # pragma once
  15 #endif
  16
  17 #include <string>
  18 #include <iterator>
  19 #include <boost/mpl/or.hpp>
  20 #include <boost/range/end.hpp>
  21 #include <boost/range/begin.hpp>
  22 #include <boost/mpl/identity.hpp>
  23 #include <boost/utility/enable_if.hpp>
  24 #include <boost/type_traits/add_const.hpp>
  25 #include <boost/type_traits/is_pointer.hpp>
  26 #include <boost/type_traits/remove_const.hpp>
  27 #include <boost/xpressive/match_results.hpp>
  28 #include <boost/xpressive/detail/detail_fwd.hpp>
  29 #include <boost/xpressive/detail/core/state.hpp>
  30 #include <boost/xpressive/detail/utility/save_restore.hpp>
  31
  32 /// INTERNAL ONLY
  33 ///
  34 #define BOOST_XPR_NONDEDUCED_TYPE_(x) typename mpl::identity<x>::type
  35
  36 namespace boost { namespace xpressive
  37 {
  38
  39 ///////////////////////////////////////////////////////////////////////////////
  40 // regex_match
  41 ///////////////////////////////////////////////////////////////////////////////
  42
  43 namespace detail
  44 {
  45     ///////////////////////////////////////////////////////////////////////////////
  46     // regex_match_impl
  47     template<typename BidiIter>
  48     inline bool regex_match_impl
  49     (
  50         BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
  51       , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
  52       , match_results<BidiIter> &what
  53       , basic_regex<BidiIter> const &re
  54       , regex_constants::match_flag_type flags = regex_constants::match_default
  55     )
  56     {
  57         typedef detail::core_access<BidiIter> access;
  58         BOOST_ASSERT(0 != re.regex_id());
  59
  60         // the state object holds matching state and
  61         // is passed by reference to all the matchers
  62         detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
  63         state.flags_.match_all_ = true;
  64         state.sub_match(0).begin_ = begin;
  65
  66         if(access::match(re, state))
  67         {
  68             access::set_prefix_suffix(what, begin, end);
  69             return true;
  70         }
  71
  72         // handle partial matches
  73         else if(state.found_partial_match_ && 0 != (flags & regex_constants::match_partial))
  74         {
  75             state.set_partial_match();
  76             return true;
  77         }
  78
  79         access::reset(what);
  80         return false;
  81     }
  82 } // namespace detail
  83
  84 /// \brief See if a regex matches a sequence from beginning to end.
  85 ///
  86 /// Determines whether there is an exact match between the regular expression \c re,
  87 /// and all of the sequence <tt>[begin, end)</tt>.
  88 ///
  89 /// \pre Type \c BidiIter meets the requirements of a Bidirectional Iterator (24.1.4).
  90 /// \pre <tt>[begin,end)</tt> denotes a valid iterator range.
  91 /// \param begin The beginning of the sequence.
  92 /// \param end The end of the sequence.
  93 /// \param what The \c match_results struct into which the sub_matches will be written
  94 /// \param re The regular expression object to use
  95 /// \param flags Optional match flags, used to control how the expression is matched
  96 ///        against the sequence. (See \c match_flag_type.)
  97 /// \return \c true if a match is found, \c false otherwise
  98 /// \throw \c regex_error on stack exhaustion
  99 template<typename BidiIter>
 100 inline bool regex_match
 101 (
 102     BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
 103   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
 104   , match_results<BidiIter> &what
 105   , basic_regex<BidiIter> const &re
 106   , regex_constants::match_flag_type flags = regex_constants::match_default
 107 )
 108 {
 109     typedef detail::core_access<BidiIter> access;
 110
 111     if(0 == re.regex_id())
 112     {
 113         access::reset(what);
 114         return false;
 115     }
 116
 117     return detail::regex_match_impl(begin, end, what, re, flags);
 118 }
 119
 120 /// \overload
 121 ///
 122 template<typename BidiIter>
 123 inline bool regex_match
 124 (
 125     BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
 126   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
 127   , basic_regex<BidiIter> const &re
 128   , regex_constants::match_flag_type flags = regex_constants::match_default
 129 )
 130 {
 131     if(0 == re.regex_id())
 132     {
 133         return false;
 134     }
 135
 136     // BUGBUG this is inefficient
 137     match_results<BidiIter> what;
 138     return detail::regex_match_impl(begin, end, what, re, flags);
 139 }
 140
 141 /// \overload
 142 ///
 143 template<typename Char>
 144 inline bool regex_match
 145 (
 146     BOOST_XPR_NONDEDUCED_TYPE_(Char) *begin
 147   , match_results<Char *> &what
 148   , basic_regex<Char *> const &re
 149   , regex_constants::match_flag_type flags = regex_constants::match_default
 150 )
 151 {
 152     typedef detail::core_access<Char *> access;
 153
 154     if(0 == re.regex_id())
 155     {
 156         access::reset(what);
 157         return false;
 158     }
 159
 160     // BUGBUG this is inefficient
 161     typedef typename remove_const<Char>::type char_type;
 162     Char *end = begin + std::char_traits<char_type>::length(begin);
 163     return detail::regex_match_impl(begin, end, what, re, flags);
 164 }
 165
 166 /// \overload
 167 ///
 168 template<typename BidiRange, typename BidiIter>
 169 inline bool regex_match
 170 (
 171     BidiRange &rng
 172   , match_results<BidiIter> &what
 173   , basic_regex<BidiIter> const &re
 174   , regex_constants::match_flag_type flags = regex_constants::match_default
 175   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 176 )
 177 {
 178     typedef detail::core_access<BidiIter> access;
 179
 180     if(0 == re.regex_id())
 181     {
 182         access::reset(what);
 183         return false;
 184     }
 185
 186     // Note that the result iterator of the range must be convertible
 187     // to BidiIter here.
 188     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 189     return detail::regex_match_impl(begin, end, what, re, flags);
 190 }
 191
 192 /// \overload
 193 ///
 194 template<typename BidiRange, typename BidiIter>
 195 inline bool regex_match
 196 (
 197     BidiRange const &rng
 198   , match_results<BidiIter> &what
 199   , basic_regex<BidiIter> const &re
 200   , regex_constants::match_flag_type flags = regex_constants::match_default
 201   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 202 )
 203 {
 204     typedef detail::core_access<BidiIter> access;
 205
 206     if(0 == re.regex_id())
 207     {
 208         access::reset(what);
 209         return false;
 210     }
 211
 212     // Note that the result iterator of the range must be convertible
 213     // to BidiIter here.
 214     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 215     return detail::regex_match_impl(begin, end, what, re, flags);
 216 }
 217
 218 /// \overload
 219 ///
 220 template<typename Char>
 221 inline bool regex_match
 222 (
 223     BOOST_XPR_NONDEDUCED_TYPE_(Char) *begin
 224   , basic_regex<Char *> const &re
 225   , regex_constants::match_flag_type flags = regex_constants::match_default
 226 )
 227 {
 228     if(0 == re.regex_id())
 229     {
 230         return false;
 231     }
 232
 233     // BUGBUG this is inefficient
 234     match_results<Char *> what;
 235     typedef typename remove_const<Char>::type char_type;
 236     Char *end = begin + std::char_traits<char_type>::length(begin);
 237     return detail::regex_match_impl(begin, end, what, re, flags);
 238 }
 239
 240 /// \overload
 241 ///
 242 template<typename BidiRange, typename BidiIter>
 243 inline bool regex_match
 244 (
 245     BidiRange &rng
 246   , basic_regex<BidiIter> const &re
 247   , regex_constants::match_flag_type flags = regex_constants::match_default
 248   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 249 )
 250 {
 251     if(0 == re.regex_id())
 252     {
 253         return false;
 254     }
 255
 256     // BUGBUG this is inefficient
 257     match_results<BidiIter> what;
 258     // Note that the result iterator of the range must be convertible
 259     // to BidiIter here.
 260     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 261     return detail::regex_match_impl(begin, end, what, re, flags);
 262 }
 263
 264 /// \overload
 265 ///
 266 template<typename BidiRange, typename BidiIter>
 267 inline bool regex_match
 268 (
 269     BidiRange const &rng
 270   , basic_regex<BidiIter> const &re
 271   , regex_constants::match_flag_type flags = regex_constants::match_default
 272   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 273 )
 274 {
 275     if(0 == re.regex_id())
 276     {
 277         return false;
 278     }
 279
 280     // BUGBUG this is inefficient
 281     match_results<BidiIter> what;
 282     // Note that the result iterator of the range must be convertible
 283     // to BidiIter here.
 284     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 285     return detail::regex_match_impl(begin, end, what, re, flags);
 286 }
 287
 288
 289 ///////////////////////////////////////////////////////////////////////////////
 290 // regex_search
 291 ///////////////////////////////////////////////////////////////////////////////
 292
 293 namespace detail
 294 {
 295     ///////////////////////////////////////////////////////////////////////////////
 296     // regex_search_impl
 297     template<typename BidiIter>
 298     inline bool regex_search_impl
 299     (
 300         match_state<BidiIter> &state
 301       , basic_regex<BidiIter> const &re
 302       , bool not_initial_null = false
 303     )
 304     {
 305         typedef core_access<BidiIter> access;
 306         typedef typename iterator_value<BidiIter>::type char_type;
 307         match_results<BidiIter> &what = *state.context_.results_ptr_;
 308         BOOST_ASSERT(0 != re.regex_id());
 309
 310         bool const partial_ok = state.flags_.match_partial_;
 311         save_restore<bool> not_null(state.flags_.match_not_null_, state.flags_.match_not_null_ || not_initial_null);
 312         state.flags_.match_prev_avail_ = state.flags_.match_prev_avail_ || !state.bos();
 313
 314         regex_impl<BidiIter> const &impl = *access::get_regex_impl(re);
 315         BidiIter const begin = state.cur_, end = state.end_;
 316         BidiIter &sub0begin = state.sub_match(0).begin_;
 317         sub0begin = state.cur_;
 318
 319         // If match_continuous is set, we only need to check for a match at the current position
 320         if(state.flags_.match_continuous_)
 321         {
 322             if(access::match(re, state))
 323             {
 324                 access::set_prefix_suffix(what, begin, end);
 325                 return true;
 326             }
 327
 328             // handle partial matches
 329             else if(partial_ok && state.found_partial_match_)
 330             {
 331                 state.set_partial_match();
 332                 return true;
 333             }
 334         }
 335
 336         // If we have a finder, use it to find where a potential match can start
 337         else if(impl.finder_ && (!partial_ok || impl.finder_->ok_for_partial_matches()))
 338         {
 339             finder<BidiIter> const &find = *impl.finder_;
 340             if(find(state))
 341             {
 342                 if(state.cur_ != begin)
 343                 {
 344                     not_null.restore();
 345                 }
 346
 347                 do
 348                 {
 349                     sub0begin = state.cur_;
 350                     if(access::match(re, state))
 351                     {
 352                         access::set_prefix_suffix(what, begin, end);
 353                         return true;
 354                     }
 355
 356                     // handle partial matches
 357                     else if(partial_ok && state.found_partial_match_)
 358                     {
 359                         state.set_partial_match();
 360                         return true;
 361                     }
 362
 363                     BOOST_ASSERT(state.cur_ == sub0begin);
 364                     not_null.restore();
 365                 }
 366                 while(state.cur_ != state.end_ && (++state.cur_, find(state)));
 367             }
 368         }
 369
 370         // Otherwise, use brute force search at every position.
 371         else
 372         {
 373             for(;;)
 374             {
 375                 if(access::match(re, state))
 376                 {
 377                     access::set_prefix_suffix(what, begin, end);
 378                     return true;
 379                 }
 380
 381                 // handle partial matches
 382                 else if(partial_ok && state.found_partial_match_)
 383                 {
 384                     state.set_partial_match();
 385                     return true;
 386                 }
 387
 388                 else if(end == sub0begin)
 389                 {
 390                     break;
 391                 }
 392
 393                 BOOST_ASSERT(state.cur_ == sub0begin);
 394                 state.cur_ = ++sub0begin;
 395                 not_null.restore();
 396             }
 397         }
 398
 399         access::reset(what);
 400         return false;
 401     }
 402 } // namespace detail
 403
 404
 405 /// \brief Determines whether there is some sub-sequence within <tt>[begin,end)</tt>
 406 /// that matches the regular expression \c re.
 407 ///
 408 /// Determines whether there is some sub-sequence within <tt>[begin,end)</tt> that matches
 409 /// the regular expression \c re.
 410 ///
 411 /// \pre Type \c BidiIter meets the requirements of a Bidirectional Iterator (24.1.4).
 412 /// \pre <tt>[begin,end)</tt> denotes a valid iterator range.
 413 /// \param begin The beginning of the sequence
 414 /// \param end The end of the sequence
 415 /// \param what The \c match_results struct into which the sub_matches will be written
 416 /// \param re The regular expression object to use
 417 /// \param flags Optional match flags, used to control how the expression is matched against
 418 ///        the sequence. (See \c match_flag_type.)
 419 /// \return \c true if a match is found, \c false otherwise
 420 /// \throw \c regex_error on stack exhaustion
 421 template<typename BidiIter>
 422 inline bool regex_search
 423 (
 424     BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
 425   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
 426   , match_results<BidiIter> &what
 427   , basic_regex<BidiIter> const &re
 428   , regex_constants::match_flag_type flags = regex_constants::match_default
 429 )
 430 {
 431     typedef detail::core_access<BidiIter> access;
 432
 433     // a default-constructed regex matches nothing
 434     if(0 == re.regex_id())
 435     {
 436         access::reset(what);
 437         return false;
 438     }
 439
 440     // the state object holds matching state and
 441     // is passed by reference to all the matchers
 442     detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 443     return detail::regex_search_impl(state, re);
 444 }
 445
 446 /// \overload
 447 ///
 448 template<typename BidiIter>
 449 inline bool regex_search
 450 (
 451     BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
 452   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
 453   , basic_regex<BidiIter> const &re
 454   , regex_constants::match_flag_type flags = regex_constants::match_default
 455 )
 456 {
 457     typedef detail::core_access<BidiIter> access;
 458
 459     // a default-constructed regex matches nothing
 460     if(0 == re.regex_id())
 461     {
 462         return false;
 463     }
 464
 465     // BUGBUG this is inefficient
 466     match_results<BidiIter> what;
 467     // the state object holds matching state and
 468     // is passed by reference to all the matchers
 469     detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 470     return detail::regex_search_impl(state, re);
 471 }
 472
 473 /// \overload
 474 ///
 475 template<typename Char>
 476 inline bool regex_search
 477 (
 478     BOOST_XPR_NONDEDUCED_TYPE_(Char) *begin
 479   , match_results<Char *> &what
 480   , basic_regex<Char *> const &re
 481   , regex_constants::match_flag_type flags = regex_constants::match_default
 482 )
 483 {
 484     typedef detail::core_access<Char *> access;
 485
 486     // a default-constructed regex matches nothing
 487     if(0 == re.regex_id())
 488     {
 489         access::reset(what);
 490         return false;
 491     }
 492
 493     // BUGBUG this is inefficient
 494     typedef typename remove_const<Char>::type char_type;
 495     Char *end = begin + std::char_traits<char_type>::length(begin);
 496     // the state object holds matching state and
 497     // is passed by reference to all the matchers
 498     detail::match_state<Char *> state(begin, end, what, *access::get_regex_impl(re), flags);
 499     return detail::regex_search_impl(state, re);
 500 }
 501
 502 /// \overload
 503 ///
 504 template<typename BidiRange, typename BidiIter>
 505 inline bool regex_search
 506 (
 507     BidiRange &rng
 508   , match_results<BidiIter> &what
 509   , basic_regex<BidiIter> const &re
 510   , regex_constants::match_flag_type flags = regex_constants::match_default
 511   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 512 )
 513 {
 514     typedef detail::core_access<BidiIter> access;
 515
 516     // a default-constructed regex matches nothing
 517     if(0 == re.regex_id())
 518     {
 519         access::reset(what);
 520         return false;
 521     }
 522
 523     // Note that the result iterator of the range must be convertible
 524     // to BidiIter here.
 525     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 526     // the state object holds matching state and
 527     // is passed by reference to all the matchers
 528     detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 529     return detail::regex_search_impl(state, re);
 530 }
 531
 532 /// \overload
 533 ///
 534 template<typename BidiRange, typename BidiIter>
 535 inline bool regex_search
 536 (
 537     BidiRange const &rng
 538   , match_results<BidiIter> &what
 539   , basic_regex<BidiIter> const &re
 540   , regex_constants::match_flag_type flags = regex_constants::match_default
 541   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 542 )
 543 {
 544     typedef detail::core_access<BidiIter> access;
 545
 546     // a default-constructed regex matches nothing
 547     if(0 == re.regex_id())
 548     {
 549         access::reset(what);
 550         return false;
 551     }
 552
 553     // Note that the result iterator of the range must be convertible
 554     // to BidiIter here.
 555     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 556     // the state object holds matching state and
 557     // is passed by reference to all the matchers
 558     detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 559     return detail::regex_search_impl(state, re);
 560 }
 561
 562 /// \overload
 563 ///
 564 template<typename Char>
 565 inline bool regex_search
 566 (
 567     BOOST_XPR_NONDEDUCED_TYPE_(Char) *begin
 568   , basic_regex<Char *> const &re
 569   , regex_constants::match_flag_type flags = regex_constants::match_default
 570 )
 571 {
 572     typedef detail::core_access<Char *> access;
 573
 574     // a default-constructed regex matches nothing
 575     if(0 == re.regex_id())
 576     {
 577         return false;
 578     }
 579
 580     // BUGBUG this is inefficient
 581     match_results<Char *> what;
 582     // BUGBUG this is inefficient
 583     typedef typename remove_const<Char>::type char_type;
 584     Char *end = begin + std::char_traits<char_type>::length(begin);
 585     // the state object holds matching state and
 586     // is passed by reference to all the matchers
 587     detail::match_state<Char *> state(begin, end, what, *access::get_regex_impl(re), flags);
 588     return detail::regex_search_impl(state, re);
 589 }
 590
 591 /// \overload
 592 ///
 593 template<typename BidiRange, typename BidiIter>
 594 inline bool regex_search
 595 (
 596     BidiRange &rng
 597   , basic_regex<BidiIter> const &re
 598   , regex_constants::match_flag_type flags = regex_constants::match_default
 599   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 600 )
 601 {
 602     typedef detail::core_access<BidiIter> access;
 603
 604     // a default-constructed regex matches nothing
 605     if(0 == re.regex_id())
 606     {
 607         return false;
 608     }
 609
 610     // BUGBUG this is inefficient
 611     match_results<BidiIter> what;
 612     // Note that the result iterator of the range must be convertible
 613     // to BidiIter here.
 614     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 615     // the state object holds matching state and
 616     // is passed by reference to all the matchers
 617     detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 618     return detail::regex_search_impl(state, re);
 619 }
 620
 621 /// \overload
 622 ///
 623 template<typename BidiRange, typename BidiIter>
 624 inline bool regex_search
 625 (
 626     BidiRange const &rng
 627   , basic_regex<BidiIter> const &re
 628   , regex_constants::match_flag_type flags = regex_constants::match_default
 629   , typename disable_if<detail::is_char_ptr<BidiRange> >::type * = 0
 630 )
 631 {
 632     typedef detail::core_access<BidiIter> access;
 633
 634     // a default-constructed regex matches nothing
 635     if(0 == re.regex_id())
 636     {
 637         return false;
 638     }
 639
 640     // BUGBUG this is inefficient
 641     match_results<BidiIter> what;
 642     // Note that the result iterator of the range must be convertible
 643     // to BidiIter here.
 644     BidiIter begin = boost::begin(rng), end = boost::end(rng);
 645     // the state object holds matching state and
 646     // is passed by reference to all the matchers
 647     detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 648     return detail::regex_search_impl(state, re);
 649 }
 650
 651
 652 ///////////////////////////////////////////////////////////////////////////////
 653 // regex_replace
 654 ///////////////////////////////////////////////////////////////////////////////
 655
 656 namespace detail
 657 {
 658     ///////////////////////////////////////////////////////////////////////////////
 659     // regex_replace_impl
 660     template<typename OutIter, typename BidiIter, typename Formatter>
 661     inline OutIter regex_replace_impl
 662     (
 663         OutIter out
 664       , BidiIter begin
 665       , BidiIter end
 666       , basic_regex<BidiIter> const &re
 667       , Formatter const &format
 668       , regex_constants::match_flag_type flags = regex_constants::match_default
 669     )
 670     {
 671         using namespace regex_constants;
 672         typedef detail::core_access<BidiIter> access;
 673         BOOST_ASSERT(0 != re.regex_id());
 674
 675         BidiIter cur = begin;
 676         match_results<BidiIter> what;
 677         detail::match_state<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
 678         bool const yes_copy = (0 == (flags & format_no_copy));
 679
 680         if(detail::regex_search_impl(state, re))
 681         {
 682             if(yes_copy)
 683             {
 684                 out = std::copy(cur, what[0].first, out);
 685             }
 686
 687             out = what.format(out, format, flags);
 688             cur = state.cur_ = state.next_search_ = what[0].second;
 689
 690             if(0 == (flags & format_first_only))
 691             {
 692                 bool not_null = (0 == what.length());
 693                 state.reset(what, *access::get_regex_impl(re));
 694                 while(detail::regex_search_impl(state, re, not_null))
 695                 {
 696                     if(yes_copy)
 697                     {
 698                         out = std::copy(cur, what[0].first, out);
 699                     }
 700
 701                     access::set_prefix_suffix(what, begin, end);
 702                     out = what.format(out, format, flags);
 703                     cur = state.cur_ = state.next_search_ = what[0].second;
 704                     not_null = (0 == what.length());
 705                     state.reset(what, *access::get_regex_impl(re));
 706                 }
 707             }
 708         }
 709
 710         if(yes_copy)
 711         {
 712             out = std::copy(cur, end, out);
 713         }
 714
 715         return out;
 716     }
 717 } // namespace detail
 718
 719 /// \brief Build an output sequence given an input sequence, a regex, and a format string or
 720 /// a formatter object, function, or expression.
 721 ///
 722 /// Constructs a \c regex_iterator object: <tt>regex_iterator\< BidiIter \> i(begin, end, re, flags)</tt>,
 723 /// and uses \c i to enumerate through all of the matches m of type <tt>match_results\< BidiIter \></tt> that
 724 /// occur within the sequence <tt>[begin, end)</tt>. If no such matches are found and <tt>!(flags \& format_no_copy)</tt>
 725 /// then calls <tt>std::copy(begin, end, out)</tt>. Otherwise, for each match found, if <tt>!(flags \& format_no_copy)</tt>
 726 /// calls <tt>std::copy(m.prefix().first, m.prefix().second, out)</tt>, and then calls <tt>m.format(out, format, flags)</tt>.
 727 /// Finally if <tt>!(flags \& format_no_copy)</tt> calls <tt>std::copy(last_m.suffix().first, last_m.suffix().second, out)</tt>
 728 /// where \c last_m is a copy of the last match found.
 729 ///
 730 /// If <tt>flags \& format_first_only</tt> is non-zero then only the first match found is replaced.
 731 ///
 732 /// \pre Type \c BidiIter meets the requirements of a Bidirectional Iterator (24.1.4).
 733 /// \pre Type \c OutIter meets the requirements of an Output Iterator (24.1.2).
 734 /// \pre Type \c Formatter models \c ForwardRange, <tt>Callable\<match_results\<BidiIter\> \></tt>,
 735 ///      <tt>Callable\<match_results\<BidiIter\>, OutIter\></tt>, or
 736 ///      <tt>Callable\<match_results\<BidiIter\>, OutIter, regex_constants::match_flag_type\></tt>;
 737 ///      or else it is a null-terminated format string, or an expression template
 738 ///      representing a formatter lambda expression.
 739 /// \pre <tt>[begin,end)</tt> denotes a valid iterator range.
 740 /// \param out An output iterator into which the output sequence is written.
 741 /// \param begin The beginning of the input sequence.
 742 /// \param end The end of the input sequence.
 743 /// \param re The regular expression object to use.
 744 /// \param format The format string used to format the replacement sequence,
 745 ///        or a formatter function, function object, or expression.
 746 /// \param flags Optional match flags, used to control how the expression is matched against
 747 ///        the sequence. (See \c match_flag_type.)
 748 /// \return The value of the output iterator after the output sequence has been written to it.
 749 /// \throw \c regex_error on stack exhaustion or invalid format string.
 750 template<typename OutIter, typename BidiIter, typename Formatter>
 751 inline OutIter regex_replace
 752 (
 753     OutIter out
 754   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
 755   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
 756   , basic_regex<BidiIter> const &re
 757   , Formatter const &format
 758   , regex_constants::match_flag_type flags = regex_constants::match_default
 759   , typename disable_if<detail::is_char_ptr<Formatter> >::type * = 0
 760 )
 761 {
 762     // Default-constructed regexes match nothing
 763     if(0 == re.regex_id())
 764     {
 765         if((0 == (flags & regex_constants::format_no_copy)))
 766         {
 767             out = std::copy(begin, end, out);
 768         }
 769
 770         return out;
 771     }
 772
 773     return detail::regex_replace_impl(out, begin, end, re, format, flags);
 774 }
 775
 776 /// \overload
 777 ///
 778 template<typename OutIter, typename BidiIter>
 779 inline OutIter regex_replace
 780 (
 781     OutIter out
 782   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) begin
 783   , BOOST_XPR_NONDEDUCED_TYPE_(BidiIter) end
 784   , basic_regex<BidiIter> const &re
 785   , typename iterator_value<BidiIter>::type const *format
 786   , regex_constants::match_flag_type flags = regex_constants::match_default
 787 )
 788 {
 789     // Default-constructed regexes match nothing
 790     if(0 == re.regex_id())
 791     {
 792         if((0 == (flags & regex_constants::format_no_copy)))
 793         {
 794             out = std::copy(begin, end, out);
 795         }
 796
 797         return out;
 798     }
 799
 800     return detail::regex_replace_impl(out, begin, end, re, format, flags);
 801 }
 802
 803 /// \overload
 804 ///
 805 template<typename BidiContainer, typename BidiIter, typename Formatter>
 806 inline BidiContainer regex_replace
 807 (
 808     BidiContainer &str
 809   , basic_regex<BidiIter> const &re
 810   , Formatter const &format
 811   , regex_constants::match_flag_type flags = regex_constants::match_default
 812   , typename disable_if<mpl::or_<detail::is_char_ptr<BidiContainer>, detail::is_char_ptr<Formatter> > >::type * = 0
 813 )
 814 {
 815     BidiContainer result;
 816     // Note that the result iterator of the range must be convertible
 817     // to BidiIter here.
 818     BidiIter begin = boost::begin(str), end = boost::end(str);
 819
 820     // Default-constructed regexes match nothing
 821     if(0 == re.regex_id())
 822     {
 823         if((0 == (flags & regex_constants::format_no_copy)))
 824         {
 825             std::copy(begin, end, std::back_inserter(result));
 826         }
 827
 828         return result;
 829     }
 830
 831     detail::regex_replace_impl(std::back_inserter(result), begin, end, re, format, flags);
 832     return result;
 833 }
 834
 835 /// \overload
 836 ///
 837 template<typename BidiContainer, typename BidiIter, typename Formatter>
 838 inline BidiContainer regex_replace
 839 (
 840     BidiContainer const &str
 841   , basic_regex<BidiIter> const &re
 842   , Formatter const &format
 843   , regex_constants::match_flag_type flags = regex_constants::match_default
 844   , typename disable_if<mpl::or_<detail::is_char_ptr<BidiContainer>, detail::is_char_ptr<Formatter> > >::type * = 0
 845 )
 846 {
 847     BidiContainer result;
 848     // Note that the result iterator of the range must be convertible
 849     // to BidiIter here.
 850     BidiIter begin = boost::begin(str), end = boost::end(str);
 851
 852     // Default-constructed regexes match nothing
 853     if(0 == re.regex_id())
 854     {
 855         if((0 == (flags & regex_constants::format_no_copy)))
 856         {
 857             std::copy(begin, end, std::back_inserter(result));
 858         }
 859
 860         return result;
 861     }
 862
 863     detail::regex_replace_impl(std::back_inserter(result), begin, end, re, format, flags);
 864     return result;
 865 }
 866
 867 /// \overload
 868 ///
 869 template<typename Char, typename Formatter>
 870 inline std::basic_string<typename remove_const<Char>::type> regex_replace
 871 (
 872     BOOST_XPR_NONDEDUCED_TYPE_(Char) *str
 873   , basic_regex<Char *> const &re
 874   , Formatter const &format
 875   , regex_constants::match_flag_type flags = regex_constants::match_default
 876   , typename disable_if<detail::is_char_ptr<Formatter> >::type * = 0
 877 )
 878 {
 879     typedef typename remove_const<Char>::type char_type;
 880     std::basic_string<char_type> result;
 881
 882     // Default-constructed regexes match nothing
 883     if(0 == re.regex_id())
 884     {
 885         if((0 == (flags & regex_constants::format_no_copy)))
 886         {
 887             result = str;
 888         }
 889
 890         return result;
 891     }
 892
 893     Char *end = str + std::char_traits<char_type>::length(str);
 894     detail::regex_replace_impl(std::back_inserter(result), str, end, re, format, flags);
 895     return result;
 896 }
 897
 898 /// \overload
 899 ///
 900 template<typename BidiContainer, typename BidiIter>
 901 inline BidiContainer regex_replace
 902 (
 903     BidiContainer &str
 904   , basic_regex<BidiIter> const &re
 905   , typename iterator_value<BidiIter>::type const *format
 906   , regex_constants::match_flag_type flags = regex_constants::match_default
 907   , typename disable_if<detail::is_char_ptr<BidiContainer> >::type * = 0
 908 )
 909 {
 910     BidiContainer result;
 911     // Note that the result iterator of the range must be convertible
 912     // to BidiIter here.
 913     BidiIter begin = boost::begin(str), end = boost::end(str);
 914
 915     // Default-constructed regexes match nothing
 916     if(0 == re.regex_id())
 917     {
 918         if((0 == (flags & regex_constants::format_no_copy)))
 919         {
 920             std::copy(begin, end, std::back_inserter(result));
 921         }
 922
 923         return result;
 924     }
 925
 926     detail::regex_replace_impl(std::back_inserter(result), begin, end, re, format, flags);
 927     return result;
 928 }
 929
 930 /// \overload
 931 ///
 932 template<typename BidiContainer, typename BidiIter>
 933 inline BidiContainer regex_replace
 934 (
 935     BidiContainer const &str
 936   , basic_regex<BidiIter> const &re
 937   , typename iterator_value<BidiIter>::type const *format
 938   , regex_constants::match_flag_type flags = regex_constants::match_default
 939   , typename disable_if<detail::is_char_ptr<BidiContainer> >::type * = 0
 940 )
 941 {
 942     BidiContainer result;
 943     // Note that the result iterator of the range must be convertible
 944     // to BidiIter here.
 945     BidiIter begin = boost::begin(str), end = boost::end(str);
 946
 947     // Default-constructed regexes match nothing
 948     if(0 == re.regex_id())
 949     {
 950         if((0 == (flags & regex_constants::format_no_copy)))
 951         {
 952             std::copy(begin, end, std::back_inserter(result));
 953         }
 954
 955         return result;
 956     }
 957
 958     detail::regex_replace_impl(std::back_inserter(result), begin, end, re, format, flags);
 959     return result;
 960 }
 961
 962 /// \overload
 963 ///
 964 template<typename Char>
 965 inline std::basic_string<typename remove_const<Char>::type> regex_replace
 966 (
 967     BOOST_XPR_NONDEDUCED_TYPE_(Char) *str
 968   , basic_regex<Char *> const &re
 969   , typename add_const<Char>::type *format
 970   , regex_constants::match_flag_type flags = regex_constants::match_default
 971 )
 972 {
 973     typedef typename remove_const<Char>::type char_type;
 974     std::basic_string<char_type> result;
 975
 976     // Default-constructed regexes match nothing
 977     if(0 == re.regex_id())
 978     {
 979         if((0 == (flags & regex_constants::format_no_copy)))
 980         {
 981             result = str;
 982         }
 983
 984         return result;
 985     }
 986
 987     Char *end = str + std::char_traits<char_type>::length(str);
 988     detail::regex_replace_impl(std::back_inserter(result), str, end, re, format, flags);
 989     return result;
 990 }
 991
 992 }} // namespace boost::xpressive
 993
 994 #endif