boost/xpressive/regex_compiler.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 /// \file regex_compiler.hpp
   3 /// Contains the definition of regex_compiler, a factory for building regex objects
   4 /// from strings.
   5 //
   6 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   7 //  Software License, Version 1.0. (See accompanying file
   8 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9
  10 #ifndef BOOST_XPRESSIVE_REGEX_COMPILER_HPP_EAN_10_04_2005
  11 #define BOOST_XPRESSIVE_REGEX_COMPILER_HPP_EAN_10_04_2005
  12
  13 // MS compatible compilers support #pragma once
  14 #if defined(_MSC_VER) && (_MSC_VER >= 1020)
  15 # pragma once
  16 #endif
  17
  18 #include <map>
  19 #include <boost/assert.hpp>
  20 #include <boost/next_prior.hpp>
  21 #include <boost/range/begin.hpp>
  22 #include <boost/range/end.hpp>
  23 #include <boost/mpl/assert.hpp>
  24 #include <boost/throw_exception.hpp>
  25 #include <boost/type_traits/is_same.hpp>
  26 #include <boost/type_traits/is_pointer.hpp>
  27 #include <boost/utility/enable_if.hpp>
  28 #include <boost/iterator/iterator_traits.hpp>
  29 #include <boost/xpressive/basic_regex.hpp>
  30 #include <boost/xpressive/detail/dynamic/parser.hpp>
  31 #include <boost/xpressive/detail/dynamic/parse_charset.hpp>
  32 #include <boost/xpressive/detail/dynamic/parser_enum.hpp>
  33 #include <boost/xpressive/detail/dynamic/parser_traits.hpp>
  34 #include <boost/xpressive/detail/core/linker.hpp>
  35 #include <boost/xpressive/detail/core/optimize.hpp>
  36
  37 namespace boost { namespace xpressive
  38 {
  39
  40 ///////////////////////////////////////////////////////////////////////////////
  41 // regex_compiler
  42 //
  43 /// \brief Class template regex_compiler is a factory for building basic_regex objects from a string.
  44 ///
  45 /// Class template regex_compiler is used to construct a basic_regex object from a string. The string
  46 /// should contain a valid regular expression. You can imbue a regex_compiler object with a locale,
  47 /// after which all basic_regex objects created with that regex_compiler object will use that locale.
  48 /// After creating a regex_compiler object, and optionally imbueing it with a locale, you can call the
  49 /// compile() method to construct a basic_regex object, passing it the string representing the regular
  50 /// expression. You can call compile() multiple times on the same regex_compiler object. Two basic_regex
  51 /// objects compiled from the same string will have different regex_id's.
  52 template<typename BidiIter, typename RegexTraits, typename CompilerTraits>
  53 struct regex_compiler
  54 {
  55     typedef BidiIter iterator_type;
  56     typedef typename iterator_value<BidiIter>::type char_type;
  57     typedef regex_constants::syntax_option_type flag_type;
  58     typedef RegexTraits traits_type;
  59     typedef typename traits_type::string_type string_type;
  60     typedef typename traits_type::locale_type locale_type;
  61     typedef typename traits_type::char_class_type char_class_type;
  62
  63     explicit regex_compiler(RegexTraits const &traits = RegexTraits())
  64       : mark_count_(0)
  65       , hidden_mark_count_(0)
  66       , traits_(traits)
  67       , upper_(0)
  68       , self_()
  69       , rules_()
  70     {
  71         this->upper_ = lookup_classname(this->rxtraits(), "upper");
  72     }
  73
  74     ///////////////////////////////////////////////////////////////////////////
  75     // imbue
  76     /// Specify the locale to be used by a regex_compiler.
  77     ///
  78     /// \param loc The locale that this regex_compiler should use.
  79     /// \return The previous locale.
  80     locale_type imbue(locale_type loc)
  81     {
  82         locale_type oldloc = this->traits_.imbue(loc);
  83         this->upper_ = lookup_classname(this->rxtraits(), "upper");
  84         return oldloc;
  85     }
  86
  87     ///////////////////////////////////////////////////////////////////////////
  88     // getloc
  89     /// Get the locale used by a regex_compiler.
  90     ///
  91     /// \return The locale used by this regex_compiler.
  92     locale_type getloc() const
  93     {
  94         return this->traits_.getloc();
  95     }
  96
  97     ///////////////////////////////////////////////////////////////////////////
  98     // compile
  99     /// Builds a basic_regex object from a range of characters.
 100     ///
 101     /// \param  begin The beginning of a range of characters representing the
 102     ///         regular expression to compile.
 103     /// \param  end The end of a range of characters representing the
 104     ///         regular expression to compile.
 105     /// \param  flags Optional bitmask that determines how the pat string is
 106     ///         interpreted. (See syntax_option_type.)
 107     /// \return A basic_regex object corresponding to the regular expression
 108     ///         represented by the character range.
 109     /// \pre    InputIter is a model of the InputIterator concept.
 110     /// \pre    [begin,end) is a valid range.
 111     /// \pre    The range of characters specified by [begin,end) contains a
 112     ///         valid string-based representation of a regular expression.
 113     /// \throw  regex_error when the range of characters has invalid regular
 114     ///         expression syntax.
 115     template<typename InputIter>
 116     basic_regex<BidiIter>
 117     compile(InputIter begin, InputIter end, flag_type flags = regex_constants::ECMAScript)
 118     {
 119         typedef typename iterator_category<InputIter>::type category;
 120         return this->compile_(begin, end, flags, category());
 121     }
 122
 123     /// \overload
 124     ///
 125     template<typename InputRange>
 126     typename disable_if<is_pointer<InputRange>, basic_regex<BidiIter> >::type
 127     compile(InputRange const &pat, flag_type flags = regex_constants::ECMAScript)
 128     {
 129         return this->compile(boost::begin(pat), boost::end(pat), flags);
 130     }
 131
 132     /// \overload
 133     ///
 134     basic_regex<BidiIter>
 135     compile(char_type const *begin, flag_type flags = regex_constants::ECMAScript)
 136     {
 137         BOOST_ASSERT(0 != begin);
 138         char_type const *end = begin + std::char_traits<char_type>::length(begin);
 139         return this->compile(begin, end, flags);
 140     }
 141
 142     /// \overload
 143     ///
 144     basic_regex<BidiIter> compile(char_type const *begin, std::size_t size, flag_type flags)
 145     {
 146         BOOST_ASSERT(0 != begin);
 147         char_type const *end = begin + size;
 148         return this->compile(begin, end, flags);
 149     }
 150
 151     ///////////////////////////////////////////////////////////////////////////
 152     // operator[]
 153     /// Return a reference to the named regular expression. If no such named
 154     /// regular expression exists, create a new regular expression and return
 155     /// a reference to it.
 156     ///
 157     /// \param  name A std::string containing the name of the regular expression.
 158     /// \pre    The string is not empty.
 159     /// \throw  bad_alloc on allocation failure.
 160     basic_regex<BidiIter> &operator [](string_type const &name)
 161     {
 162         BOOST_ASSERT(!name.empty());
 163         return this->rules_[name];
 164     }
 165
 166     /// \overload
 167     ///
 168     basic_regex<BidiIter> const &operator [](string_type const &name) const
 169     {
 170         BOOST_ASSERT(!name.empty());
 171         return this->rules_[name];
 172     }
 173
 174 private:
 175
 176     typedef detail::escape_value<char_type, char_class_type> escape_value;
 177     typedef detail::alternate_matcher<detail::alternates_vector<BidiIter>, RegexTraits> alternate_matcher;
 178
 179     ///////////////////////////////////////////////////////////////////////////
 180     // compile_
 181     /// INTERNAL ONLY
 182     template<typename FwdIter>
 183     basic_regex<BidiIter> compile_(FwdIter begin, FwdIter end, flag_type flags, std::forward_iterator_tag)
 184     {
 185         BOOST_MPL_ASSERT((is_same<char_type, typename iterator_value<FwdIter>::type>));
 186         using namespace regex_constants;
 187         this->reset();
 188         this->traits_.flags(flags);
 189
 190         basic_regex<BidiIter> rextmp, *prex = &rextmp;
 191         FwdIter tmp = begin;
 192
 193         // Check if this regex is a named rule:
 194         string_type name;
 195         if(token_group_begin == this->traits_.get_token(tmp, end) &&
 196            BOOST_XPR_ENSURE_(tmp != end, error_paren, "mismatched parenthesis") &&
 197            token_rule_assign == this->traits_.get_group_type(tmp, end, name))
 198         {
 199             begin = tmp;
 200             BOOST_XPR_ENSURE_
 201             (
 202                 begin != end && token_group_end == this->traits_.get_token(begin, end)
 203               , error_paren
 204               , "mismatched parenthesis"
 205             );
 206             prex = &this->rules_[name];
 207         }
 208
 209         this->self_ = detail::core_access<BidiIter>::get_regex_impl(*prex);
 210
 211         // at the top level, a regex is a sequence of alternates
 212         detail::sequence<BidiIter> seq = this->parse_alternates(begin, end);
 213         BOOST_XPR_ENSURE_(begin == end, error_paren, "mismatched parenthesis");
 214
 215         // terminate the sequence
 216         seq += detail::make_dynamic<BidiIter>(detail::end_matcher());
 217
 218         // bundle the regex information into a regex_impl object
 219         detail::common_compile(seq.xpr().matchable(), *this->self_, this->rxtraits());
 220
 221         this->self_->traits_ = new detail::traits_holder<RegexTraits>(this->rxtraits());
 222         this->self_->mark_count_ = this->mark_count_;
 223         this->self_->hidden_mark_count_ = this->hidden_mark_count_;
 224
 225         // References changed, update dependencies.
 226         this->self_->tracking_update();
 227         this->self_.reset();
 228         return *prex;
 229     }
 230
 231     ///////////////////////////////////////////////////////////////////////////
 232     // compile_
 233     /// INTERNAL ONLY
 234     template<typename InputIter>
 235     basic_regex<BidiIter> compile_(InputIter begin, InputIter end, flag_type flags, std::input_iterator_tag)
 236     {
 237         string_type pat(begin, end);
 238         return this->compile_(boost::begin(pat), boost::end(pat), flags, std::forward_iterator_tag());
 239     }
 240
 241     ///////////////////////////////////////////////////////////////////////////
 242     // reset
 243     /// INTERNAL ONLY
 244     void reset()
 245     {
 246         this->mark_count_ = 0;
 247         this->hidden_mark_count_ = 0;
 248         this->traits_.flags(regex_constants::ECMAScript);
 249     }
 250
 251     ///////////////////////////////////////////////////////////////////////////
 252     // regex_traits
 253     /// INTERNAL ONLY
 254     traits_type &rxtraits()
 255     {
 256         return this->traits_.traits();
 257     }
 258
 259     ///////////////////////////////////////////////////////////////////////////
 260     // regex_traits
 261     /// INTERNAL ONLY
 262     traits_type const &rxtraits() const
 263     {
 264         return this->traits_.traits();
 265     }
 266
 267     ///////////////////////////////////////////////////////////////////////////
 268     // parse_alternates
 269     /// INTERNAL ONLY
 270     template<typename FwdIter>
 271     detail::sequence<BidiIter> parse_alternates(FwdIter &begin, FwdIter end)
 272     {
 273         using namespace regex_constants;
 274         int count = 0;
 275         FwdIter tmp = begin;
 276         detail::sequence<BidiIter> seq;
 277
 278         do switch(++count)
 279         {
 280         case 1:
 281             seq = this->parse_sequence(tmp, end);
 282             break;
 283         case 2:
 284             seq = detail::make_dynamic<BidiIter>(alternate_matcher()) | seq;
 285             // fall-through
 286         default:
 287             seq |= this->parse_sequence(tmp, end);
 288         }
 289         while((begin = tmp) != end && token_alternate == this->traits_.get_token(tmp, end));
 290
 291         return seq;
 292     }
 293
 294     ///////////////////////////////////////////////////////////////////////////
 295     // parse_group
 296     /// INTERNAL ONLY
 297     template<typename FwdIter>
 298     detail::sequence<BidiIter> parse_group(FwdIter &begin, FwdIter end)
 299     {
 300         using namespace regex_constants;
 301         int mark_nbr = 0;
 302         bool keeper = false;
 303         bool lookahead = false;
 304         bool lookbehind = false;
 305         bool negative = false;
 306         string_type name;
 307
 308         detail::sequence<BidiIter> seq, seq_end;
 309         FwdIter tmp = FwdIter();
 310
 311         syntax_option_type old_flags = this->traits_.flags();
 312
 313         switch(this->traits_.get_group_type(begin, end, name))
 314         {
 315         case token_no_mark:
 316             // Don't process empty groups like (?:) or (?i)
 317             // BUGBUG this doesn't handle the degenerate (?:)+ correctly
 318             if(token_group_end == this->traits_.get_token(tmp = begin, end))
 319             {
 320                 return this->parse_atom(begin = tmp, end);
 321             }
 322             break;
 323
 324         case token_negative_lookahead:
 325             negative = true; // fall-through
 326         case token_positive_lookahead:
 327             lookahead = true;
 328             break;
 329
 330         case token_negative_lookbehind:
 331             negative = true; // fall-through
 332         case token_positive_lookbehind:
 333             lookbehind = true;
 334             break;
 335
 336         case token_independent_sub_expression:
 337             keeper = true;
 338             break;
 339
 340         case token_comment:
 341             while(BOOST_XPR_ENSURE_(begin != end, error_paren, "mismatched parenthesis"))
 342             {
 343                 switch(this->traits_.get_token(begin, end))
 344                 {
 345                 case token_group_end: return this->parse_atom(begin, end);
 346                 case token_escape: BOOST_XPR_ENSURE_(begin != end, error_escape, "incomplete escape sequence");
 347                 case token_literal: ++begin;
 348                 default:;
 349                 }
 350             }
 351             break;
 352
 353         case token_recurse:
 354             BOOST_XPR_ENSURE_
 355             (
 356                 begin != end && token_group_end == this->traits_.get_token(begin, end)
 357               , error_paren
 358               , "mismatched parenthesis"
 359             );
 360             return detail::make_dynamic<BidiIter>(detail::regex_byref_matcher<BidiIter>(this->self_));
 361
 362         case token_rule_assign:
 363             BOOST_THROW_EXCEPTION(
 364                 regex_error(error_badrule, "rule assignments must be at the front of the regex")
 365             );
 366             break;
 367
 368         case token_rule_ref:
 369             {
 370                 typedef detail::core_access<BidiIter> access;
 371                 BOOST_XPR_ENSURE_
 372                 (
 373                     begin != end && token_group_end == this->traits_.get_token(begin, end)
 374                   , error_paren
 375                   , "mismatched parenthesis"
 376                 );
 377                 basic_regex<BidiIter> &rex = this->rules_[name];
 378                 shared_ptr<detail::regex_impl<BidiIter> > impl = access::get_regex_impl(rex);
 379                 this->self_->track_reference(*impl);
 380                 return detail::make_dynamic<BidiIter>(detail::regex_byref_matcher<BidiIter>(impl));
 381             }
 382
 383         case token_named_mark:
 384             mark_nbr = static_cast<int>(++this->mark_count_);
 385             for(std::size_t i = 0; i < this->self_->named_marks_.size(); ++i)
 386             {
 387                 BOOST_XPR_ENSURE_(this->self_->named_marks_[i].name_ != name, error_badmark, "named mark already exists");
 388             }
 389             this->self_->named_marks_.push_back(detail::named_mark<char_type>(name, this->mark_count_));
 390             seq = detail::make_dynamic<BidiIter>(detail::mark_begin_matcher(mark_nbr));
 391             seq_end = detail::make_dynamic<BidiIter>(detail::mark_end_matcher(mark_nbr));
 392             break;
 393
 394         case token_named_mark_ref:
 395             BOOST_XPR_ENSURE_
 396             (
 397                 begin != end && token_group_end == this->traits_.get_token(begin, end)
 398               , error_paren
 399               , "mismatched parenthesis"
 400             );
 401             for(std::size_t i = 0; i < this->self_->named_marks_.size(); ++i)
 402             {
 403                 if(this->self_->named_marks_[i].name_ == name)
 404                 {
 405                     mark_nbr = static_cast<int>(this->self_->named_marks_[i].mark_nbr_);
 406                     return detail::make_backref_xpression<BidiIter>
 407                     (
 408                         mark_nbr, this->traits_.flags(), this->rxtraits()
 409                     );
 410                 }
 411             }
 412             BOOST_THROW_EXCEPTION(regex_error(error_badmark, "invalid named back-reference"));
 413             break;
 414
 415         default:
 416             mark_nbr = static_cast<int>(++this->mark_count_);
 417             seq = detail::make_dynamic<BidiIter>(detail::mark_begin_matcher(mark_nbr));
 418             seq_end = detail::make_dynamic<BidiIter>(detail::mark_end_matcher(mark_nbr));
 419             break;
 420         }
 421
 422         // alternates
 423         seq += this->parse_alternates(begin, end);
 424         seq += seq_end;
 425         BOOST_XPR_ENSURE_
 426         (
 427             begin != end && token_group_end == this->traits_.get_token(begin, end)
 428           , error_paren
 429           , "mismatched parenthesis"
 430         );
 431
 432         typedef detail::shared_matchable<BidiIter> xpr_type;
 433         if(lookahead)
 434         {
 435             seq += detail::make_independent_end_xpression<BidiIter>(seq.pure());
 436             detail::lookahead_matcher<xpr_type> lookahead(seq.xpr(), negative, seq.pure());
 437             seq = detail::make_dynamic<BidiIter>(lookahead);
 438         }
 439         else if(lookbehind)
 440         {
 441             seq += detail::make_independent_end_xpression<BidiIter>(seq.pure());
 442             detail::lookbehind_matcher<xpr_type> lookbehind(seq.xpr(), seq.width().value(), negative, seq.pure());
 443             seq = detail::make_dynamic<BidiIter>(lookbehind);
 444         }
 445         else if(keeper) // independent sub-expression
 446         {
 447             seq += detail::make_independent_end_xpression<BidiIter>(seq.pure());
 448             detail::keeper_matcher<xpr_type> keeper(seq.xpr(), seq.pure());
 449             seq = detail::make_dynamic<BidiIter>(keeper);
 450         }
 451
 452         // restore the modifiers
 453         this->traits_.flags(old_flags);
 454         return seq;
 455     }
 456
 457     ///////////////////////////////////////////////////////////////////////////
 458     // parse_charset
 459     /// INTERNAL ONLY
 460     template<typename FwdIter>
 461     detail::sequence<BidiIter> parse_charset(FwdIter &begin, FwdIter end)
 462     {
 463         detail::compound_charset<traits_type> chset;
 464
 465         // call out to a helper to actually parse the character set
 466         detail::parse_charset(begin, end, chset, this->traits_);
 467
 468         return detail::make_charset_xpression<BidiIter>
 469         (
 470             chset
 471           , this->rxtraits()
 472           , this->traits_.flags()
 473         );
 474     }
 475
 476     ///////////////////////////////////////////////////////////////////////////
 477     // parse_atom
 478     /// INTERNAL ONLY
 479     template<typename FwdIter>
 480     detail::sequence<BidiIter> parse_atom(FwdIter &begin, FwdIter end)
 481     {
 482         using namespace regex_constants;
 483         escape_value esc = { 0, 0, 0, detail::escape_char };
 484         FwdIter old_begin = begin;
 485
 486         switch(this->traits_.get_token(begin, end))
 487         {
 488         case token_literal:
 489             return detail::make_literal_xpression<BidiIter>
 490             (
 491                 this->parse_literal(begin, end), this->traits_.flags(), this->rxtraits()
 492             );
 493
 494         case token_any:
 495             return detail::make_any_xpression<BidiIter>(this->traits_.flags(), this->rxtraits());
 496
 497         case token_assert_begin_sequence:
 498             return detail::make_dynamic<BidiIter>(detail::assert_bos_matcher());
 499
 500         case token_assert_end_sequence:
 501             return detail::make_dynamic<BidiIter>(detail::assert_eos_matcher());
 502
 503         case token_assert_begin_line:
 504             return detail::make_assert_begin_line<BidiIter>(this->traits_.flags(), this->rxtraits());
 505
 506         case token_assert_end_line:
 507             return detail::make_assert_end_line<BidiIter>(this->traits_.flags(), this->rxtraits());
 508
 509         case token_assert_word_boundary:
 510             return detail::make_assert_word<BidiIter>(detail::word_boundary<mpl::true_>(), this->rxtraits());
 511
 512         case token_assert_not_word_boundary:
 513             return detail::make_assert_word<BidiIter>(detail::word_boundary<mpl::false_>(), this->rxtraits());
 514
 515         case token_assert_word_begin:
 516             return detail::make_assert_word<BidiIter>(detail::word_begin(), this->rxtraits());
 517
 518         case token_assert_word_end:
 519             return detail::make_assert_word<BidiIter>(detail::word_end(), this->rxtraits());
 520
 521         case token_escape:
 522             esc = this->parse_escape(begin, end);
 523             switch(esc.type_)
 524             {
 525             case detail::escape_mark:
 526                 return detail::make_backref_xpression<BidiIter>
 527                 (
 528                     esc.mark_nbr_, this->traits_.flags(), this->rxtraits()
 529                 );
 530             case detail::escape_char:
 531                 return detail::make_char_xpression<BidiIter>
 532                 (
 533                     esc.ch_, this->traits_.flags(), this->rxtraits()
 534                 );
 535             case detail::escape_class:
 536                 return detail::make_posix_charset_xpression<BidiIter>
 537                 (
 538                     esc.class_
 539                   , this->is_upper_(*begin++)
 540                   , this->traits_.flags()
 541                   , this->rxtraits()
 542                 );
 543             }
 544
 545         case token_group_begin:
 546             return this->parse_group(begin, end);
 547
 548         case token_charset_begin:
 549             return this->parse_charset(begin, end);
 550
 551         case token_invalid_quantifier:
 552             BOOST_THROW_EXCEPTION(regex_error(error_badrepeat, "quantifier not expected"));
 553             break;
 554
 555         case token_quote_meta_begin:
 556             return detail::make_literal_xpression<BidiIter>
 557             (
 558                 this->parse_quote_meta(begin, end), this->traits_.flags(), this->rxtraits()
 559             );
 560
 561         case token_quote_meta_end:
 562             BOOST_THROW_EXCEPTION(
 563                 regex_error(
 564                     error_escape
 565                   , "found quote-meta end without corresponding quote-meta begin"
 566                 )
 567             );
 568             break;
 569
 570         case token_end_of_pattern:
 571             break;
 572
 573         default:
 574             begin = old_begin;
 575             break;
 576         }
 577
 578         return detail::sequence<BidiIter>();
 579     }
 580
 581     ///////////////////////////////////////////////////////////////////////////
 582     // parse_quant
 583     /// INTERNAL ONLY
 584     template<typename FwdIter>
 585     detail::sequence<BidiIter> parse_quant(FwdIter &begin, FwdIter end)
 586     {
 587         BOOST_ASSERT(begin != end);
 588         detail::quant_spec spec = { 0, 0, false, &this->hidden_mark_count_ };
 589         detail::sequence<BidiIter> seq = this->parse_atom(begin, end);
 590
 591         // BUGBUG this doesn't handle the degenerate (?:)+ correctly
 592         if(!seq.empty() && begin != end && detail::quant_none != seq.quant())
 593         {
 594             if(this->traits_.get_quant_spec(begin, end, spec))
 595             {
 596                 BOOST_ASSERT(spec.min_ <= spec.max_);
 597
 598                 if(0 == spec.max_) // quant {0,0} is degenerate -- matches nothing.
 599                 {
 600                     seq = this->parse_quant(begin, end);
 601                 }
 602                 else
 603                 {
 604                     seq.repeat(spec);
 605                 }
 606             }
 607         }
 608
 609         return seq;
 610     }
 611
 612     ///////////////////////////////////////////////////////////////////////////
 613     // parse_sequence
 614     /// INTERNAL ONLY
 615     template<typename FwdIter>
 616     detail::sequence<BidiIter> parse_sequence(FwdIter &begin, FwdIter end)
 617     {
 618         detail::sequence<BidiIter> seq;
 619
 620         while(begin != end)
 621         {
 622             detail::sequence<BidiIter> seq_quant = this->parse_quant(begin, end);
 623
 624             // did we find a quantified atom?
 625             if(seq_quant.empty())
 626                 break;
 627
 628             // chain it to the end of the xpression sequence
 629             seq += seq_quant;
 630         }
 631
 632         return seq;
 633     }
 634
 635     ///////////////////////////////////////////////////////////////////////////
 636     // parse_literal
 637     //  scan ahead looking for char literals to be globbed together into a string literal
 638     /// INTERNAL ONLY
 639     template<typename FwdIter>
 640     string_type parse_literal(FwdIter &begin, FwdIter end)
 641     {
 642         using namespace regex_constants;
 643         BOOST_ASSERT(begin != end);
 644         BOOST_ASSERT(token_literal == this->traits_.get_token(begin, end));
 645         escape_value esc = { 0, 0, 0, detail::escape_char };
 646         string_type literal(1, *begin);
 647
 648         for(FwdIter prev = begin, tmp = ++begin; begin != end; prev = begin, begin = tmp)
 649         {
 650             detail::quant_spec spec = { 0, 0, false, &this->hidden_mark_count_ };
 651             if(this->traits_.get_quant_spec(tmp, end, spec))
 652             {
 653                 if(literal.size() != 1)
 654                 {
 655                     begin = prev;
 656                     literal.erase(boost::prior(literal.end()));
 657                 }
 658                 return literal;
 659             }
 660             else switch(this->traits_.get_token(tmp, end))
 661             {
 662             case token_escape:
 663                 esc = this->parse_escape(tmp, end);
 664                 if(detail::escape_char != esc.type_) return literal;
 665                 literal.insert(literal.end(), esc.ch_);
 666                 break;
 667             case token_literal:
 668                 literal.insert(literal.end(), *tmp++);
 669                 break;
 670             default:
 671                 return literal;
 672             }
 673         }
 674
 675         return literal;
 676     }
 677
 678     ///////////////////////////////////////////////////////////////////////////
 679     // parse_quote_meta
 680     //  scan ahead looking for char literals to be globbed together into a string literal
 681     /// INTERNAL ONLY
 682     template<typename FwdIter>
 683     string_type parse_quote_meta(FwdIter &begin, FwdIter end)
 684     {
 685         using namespace regex_constants;
 686         FwdIter old_begin = begin, old_end;
 687         while(end != (old_end = begin))
 688         {
 689             switch(this->traits_.get_token(begin, end))
 690             {
 691             case token_quote_meta_end: return string_type(old_begin, old_end);
 692             case token_escape: BOOST_XPR_ENSURE_(begin != end, error_escape, "incomplete escape sequence");
 693             case token_literal: ++begin;
 694             default:;
 695             }
 696         }
 697         return string_type(old_begin, begin);
 698     }
 699
 700     ///////////////////////////////////////////////////////////////////////////////
 701     // parse_escape
 702     /// INTERNAL ONLY
 703     template<typename FwdIter>
 704     escape_value parse_escape(FwdIter &begin, FwdIter end)
 705     {
 706         BOOST_XPR_ENSURE_(begin != end, regex_constants::error_escape, "incomplete escape sequence");
 707
 708         // first, check to see if this can be a backreference
 709         if(0 < this->rxtraits().value(*begin, 10))
 710         {
 711             // Parse at most 3 decimal digits.
 712             FwdIter tmp = begin;
 713             int mark_nbr = detail::toi(tmp, end, this->rxtraits(), 10, 999);
 714
 715             // If the resulting number could conceivably be a backref, then it is.
 716             if(10 > mark_nbr || mark_nbr <= static_cast<int>(this->mark_count_))
 717             {
 718                 begin = tmp;
 719                 escape_value esc = {0, mark_nbr, 0, detail::escape_mark};
 720                 return esc;
 721             }
 722         }
 723
 724         // Not a backreference, defer to the parse_escape helper
 725         return detail::parse_escape(begin, end, this->traits_);
 726     }
 727
 728     bool is_upper_(char_type ch) const
 729     {
 730         return 0 != this->upper_ && this->rxtraits().isctype(ch, this->upper_);
 731     }
 732
 733     std::size_t mark_count_;
 734     std::size_t hidden_mark_count_;
 735     CompilerTraits traits_;
 736     typename RegexTraits::char_class_type upper_;
 737     shared_ptr<detail::regex_impl<BidiIter> > self_;
 738     std::map<string_type, basic_regex<BidiIter> > rules_;
 739 };
 740
 741 }} // namespace boost::xpressive
 742
 743 #endif