3rdparty/boost/boost/regex/v4/perl_matcher.hpp

   1 /*
   2  *
   3  * Copyright (c) 2002
   4  * John Maddock
   5  *
   6  * Use, modification and distribution are subject to the
   7  * Boost 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  */
  11
  12 #ifndef BOOST_REGEX_MATCHER_HPP
  13 #define BOOST_REGEX_MATCHER_HPP
  14
  15 #include <boost/regex/v4/iterator_category.hpp>
  16
  17 #ifdef BOOST_MSVC
  18 #pragma warning(push)
  19 #pragma warning(disable: 4103)
  20 #endif
  21 #ifdef BOOST_HAS_ABI_HEADERS
  22 #  include BOOST_ABI_PREFIX
  23 #endif
  24 #ifdef BOOST_MSVC
  25 #pragma warning(pop)
  26 #endif
  27
  28 #ifdef BOOST_MSVC
  29 #  pragma warning(push)
  30 #  pragma warning(disable: 4800)
  31 #endif
  32
  33 namespace boost{
  34 namespace BOOST_REGEX_DETAIL_NS{
  35
  36 //
  37 // error checking API:
  38 //
  39 BOOST_REGEX_DECL void BOOST_REGEX_CALL verify_options(boost::regex_constants::syntax_option_type ef, match_flag_type mf);
  40 //
  41 // function can_start:
  42 //
  43 template <class charT>
  44 inline bool can_start(charT c, const unsigned char* map, unsigned char mask)
  45 {
  46    return ((c < static_cast<charT>(0)) ? true : ((c >= static_cast<charT>(1 << CHAR_BIT)) ? true : map[c] & mask));
  47 }
  48 inline bool can_start(char c, const unsigned char* map, unsigned char mask)
  49 {
  50    return map[(unsigned char)c] & mask;
  51 }
  52 inline bool can_start(signed char c, const unsigned char* map, unsigned char mask)
  53 {
  54    return map[(unsigned char)c] & mask;
  55 }
  56 inline bool can_start(unsigned char c, const unsigned char* map, unsigned char mask)
  57 {
  58    return map[c] & mask;
  59 }
  60 inline bool can_start(unsigned short c, const unsigned char* map, unsigned char mask)
  61 {
  62    return ((c >= (1 << CHAR_BIT)) ? true : map[c] & mask);
  63 }
  64 #if !defined(__hpux) && !defined(__WINSCW__)// WCHAR_MIN not usable in pp-directives.
  65 #if defined(WCHAR_MIN) && (WCHAR_MIN == 0) && !defined(BOOST_NO_INTRINSIC_WCHAR_T)
  66 inline bool can_start(wchar_t c, const unsigned char* map, unsigned char mask)
  67 {
  68    return ((c >= static_cast<wchar_t>(1u << CHAR_BIT)) ? true : map[c] & mask);
  69 }
  70 #endif
  71 #endif
  72 #if !defined(BOOST_NO_INTRINSIC_WCHAR_T)
  73 inline bool can_start(unsigned int c, const unsigned char* map, unsigned char mask)
  74 {
  75    return (((c >= static_cast<unsigned int>(1u << CHAR_BIT)) ? true : map[c] & mask));
  76 }
  77 #endif
  78
  79
  80 //
  81 // Unfortunately Rogue Waves standard library appears to have a bug
  82 // in std::basic_string::compare that results in eroneous answers
  83 // in some cases (tested with Borland C++ 5.1, Rogue Wave lib version
  84 // 0x020101) the test case was:
  85 // {39135,0} < {0xff,0}
  86 // which succeeds when it should not.
  87 //
  88 #ifndef _RWSTD_VER
  89 template <class C, class T, class A>
  90 inline int string_compare(const std::basic_string<C,T,A>& s, const C* p)
  91 {
  92    if(0 == *p)
  93    {
  94       if(s.empty() || ((s.size() == 1) && (s[0] == 0)))
  95          return 0;
  96    }
  97    return s.compare(p);
  98 }
  99 #else
 100 template <class C, class T, class A>
 101 inline int string_compare(const std::basic_string<C,T,A>& s, const C* p)
 102 {
 103    if(0 == *p)
 104    {
 105       if(s.empty() || ((s.size() == 1) && (s[0] == 0)))
 106          return 0;
 107    }
 108    return s.compare(p);
 109 }
 110 inline int string_compare(const std::string& s, const char* p)
 111 { return std::strcmp(s.c_str(), p); }
 112 # ifndef BOOST_NO_WREGEX
 113 inline int string_compare(const std::wstring& s, const wchar_t* p)
 114 { return std::wcscmp(s.c_str(), p); }
 115 #endif
 116 #endif
 117 template <class Seq, class C>
 118 inline int string_compare(const Seq& s, const C* p)
 119 {
 120    std::size_t i = 0;
 121    while((i < s.size()) && (p[i] == s[i]))
 122    {
 123       ++i;
 124    }
 125    return (i == s.size()) ? -p[i] : s[i] - p[i];
 126 }
 127 # define STR_COMP(s,p) string_compare(s,p)
 128
 129 template<class charT>
 130 inline const charT* re_skip_past_null(const charT* p)
 131 {
 132   while (*p != static_cast<charT>(0)) ++p;
 133   return ++p;
 134 }
 135
 136 template <class iterator, class charT, class traits_type, class char_classT>
 137 iterator BOOST_REGEX_CALL re_is_set_member(iterator next,
 138                           iterator last,
 139                           const re_set_long<char_classT>* set_,
 140                           const regex_data<charT, traits_type>& e, bool icase)
 141 {
 142    const charT* p = reinterpret_cast<const charT*>(set_+1);
 143    iterator ptr;
 144    unsigned int i;
 145    //bool icase = e.m_flags & regex_constants::icase;
 146
 147    if(next == last) return next;
 148
 149    typedef typename traits_type::string_type traits_string_type;
 150    const ::boost::regex_traits_wrapper<traits_type>& traits_inst = *(e.m_ptraits);
 151
 152    // dwa 9/13/00 suppress incorrect MSVC warning - it claims this is never
 153    // referenced
 154    (void)traits_inst;
 155
 156    // try and match a single character, could be a multi-character
 157    // collating element...
 158    for(i = 0; i < set_->csingles; ++i)
 159    {
 160       ptr = next;
 161       if(*p == static_cast<charT>(0))
 162       {
 163          // treat null string as special case:
 164          if(traits_inst.translate(*ptr, icase))
 165          {
 166             ++p;
 167             continue;
 168          }
 169          return set_->isnot ? next : (ptr == next) ? ++next : ptr;
 170       }
 171       else
 172       {
 173          while(*p && (ptr != last))
 174          {
 175             if(traits_inst.translate(*ptr, icase) != *p)
 176                break;
 177             ++p;
 178             ++ptr;
 179          }
 180
 181          if(*p == static_cast<charT>(0)) // if null we've matched
 182             return set_->isnot ? next : (ptr == next) ? ++next : ptr;
 183
 184          p = re_skip_past_null(p);     // skip null
 185       }
 186    }
 187
 188    charT col = traits_inst.translate(*next, icase);
 189
 190
 191    if(set_->cranges || set_->cequivalents)
 192    {
 193       traits_string_type s1;
 194       //
 195       // try and match a range, NB only a single character can match
 196       if(set_->cranges)
 197       {
 198          if((e.m_flags & regex_constants::collate) == 0)
 199             s1.assign(1, col);
 200          else
 201          {
 202             charT a[2] = { col, charT(0), };
 203             s1 = traits_inst.transform(a, a + 1);
 204          }
 205          for(i = 0; i < set_->cranges; ++i)
 206          {
 207             if(STR_COMP(s1, p) >= 0)
 208             {
 209                do{ ++p; }while(*p);
 210                ++p;
 211                if(STR_COMP(s1, p) <= 0)
 212                   return set_->isnot ? next : ++next;
 213             }
 214             else
 215             {
 216                // skip first string
 217                do{ ++p; }while(*p);
 218                ++p;
 219             }
 220             // skip second string
 221             do{ ++p; }while(*p);
 222             ++p;
 223          }
 224       }
 225       //
 226       // try and match an equivalence class, NB only a single character can match
 227       if(set_->cequivalents)
 228       {
 229          charT a[2] = { col, charT(0), };
 230          s1 = traits_inst.transform_primary(a, a +1);
 231          for(i = 0; i < set_->cequivalents; ++i)
 232          {
 233             if(STR_COMP(s1, p) == 0)
 234                return set_->isnot ? next : ++next;
 235             // skip string
 236             do{ ++p; }while(*p);
 237             ++p;
 238          }
 239       }
 240    }
 241    if(traits_inst.isctype(col, set_->cclasses) == true)
 242       return set_->isnot ? next : ++next;
 243    if((set_->cnclasses != 0) && (traits_inst.isctype(col, set_->cnclasses) == false))
 244       return set_->isnot ? next : ++next;
 245    return set_->isnot ? ++next : next;
 246 }
 247
 248 template <class BidiIterator>
 249 class repeater_count
 250 {
 251    repeater_count** stack;
 252    repeater_count* next;
 253    int state_id;
 254    std::size_t count;        // the number of iterations so far
 255    BidiIterator start_pos;   // where the last repeat started
 256
 257    repeater_count* unwind_until(int n, repeater_count* p, int current_recursion_id)
 258    {
 259       while(p && (p->state_id != n))
 260       {
 261          if(-2 - current_recursion_id == p->state_id)
 262             return 0;
 263          p = p->next;
 264          if(p && (p->state_id < 0))
 265          {
 266             p = unwind_until(p->state_id, p, current_recursion_id);
 267             if(!p)
 268                return p;
 269             p = p->next;
 270          }
 271       }
 272       return p;
 273    }
 274 public:
 275    repeater_count(repeater_count** s) : stack(s), next(0), state_id(-1), count(0), start_pos() {}
 276
 277    repeater_count(int i, repeater_count** s, BidiIterator start, int current_recursion_id)
 278       : start_pos(start)
 279    {
 280       state_id = i;
 281       stack = s;
 282       next = *stack;
 283       *stack = this;
 284       if((state_id > next->state_id) && (next->state_id >= 0))
 285          count = 0;
 286       else
 287       {
 288          repeater_count* p = next;
 289          p = unwind_until(state_id, p, current_recursion_id);
 290          if(p)
 291          {
 292             count = p->count;
 293             start_pos = p->start_pos;
 294          }
 295          else
 296             count = 0;
 297       }
 298    }
 299    ~repeater_count()
 300    {
 301       if(next)
 302          *stack = next;
 303    }
 304    std::size_t get_count() { return count; }
 305    int get_id() { return state_id; }
 306    std::size_t operator++() { return ++count; }
 307    bool check_null_repeat(const BidiIterator& pos, std::size_t max)
 308    {
 309       // this is called when we are about to start a new repeat,
 310       // if the last one was NULL move our count to max,
 311       // otherwise save the current position.
 312       bool result = (count == 0) ? false : (pos == start_pos);
 313       if(result)
 314          count = max;
 315       else
 316          start_pos = pos;
 317       return result;
 318    }
 319 };
 320
 321 struct saved_state;
 322
 323 enum saved_state_type
 324 {
 325    saved_type_end = 0,
 326    saved_type_paren = 1,
 327    saved_type_recurse = 2,
 328    saved_type_assertion = 3,
 329    saved_state_alt = 4,
 330    saved_state_repeater_count = 5,
 331    saved_state_extra_block = 6,
 332    saved_state_greedy_single_repeat = 7,
 333    saved_state_rep_slow_dot = 8,
 334    saved_state_rep_fast_dot = 9,
 335    saved_state_rep_char = 10,
 336    saved_state_rep_short_set = 11,
 337    saved_state_rep_long_set = 12,
 338    saved_state_non_greedy_long_repeat = 13,
 339    saved_state_count = 14
 340 };
 341
 342 template <class Results>
 343 struct recursion_info
 344 {
 345    typedef typename Results::value_type value_type;
 346    typedef typename value_type::iterator iterator;
 347    int idx;
 348    const re_syntax_base* preturn_address;
 349    Results results;
 350    repeater_count<iterator>* repeater_stack;
 351    iterator location_of_start;
 352 };
 353
 354 #ifdef BOOST_MSVC
 355 #pragma warning(push)
 356 #pragma warning(disable : 4251 4231)
 357 #  if BOOST_MSVC < 1600
 358 #     pragma warning(disable : 4660)
 359 #  endif
 360 #endif
 361
 362 template <class BidiIterator, class Allocator, class traits>
 363 class perl_matcher
 364 {
 365 public:
 366    typedef typename traits::char_type char_type;
 367    typedef perl_matcher<BidiIterator, Allocator, traits> self_type;
 368    typedef bool (self_type::*matcher_proc_type)(void);
 369    typedef std::size_t traits_size_type;
 370    typedef typename is_byte<char_type>::width_type width_type;
 371    typedef typename regex_iterator_traits<BidiIterator>::difference_type difference_type;
 372    typedef match_results<BidiIterator, Allocator> results_type;
 373
 374    perl_matcher(BidiIterator first, BidiIterator end,
 375       match_results<BidiIterator, Allocator>& what,
 376       const basic_regex<char_type, traits>& e,
 377       match_flag_type f,
 378       BidiIterator l_base)
 379       :  m_result(what), base(first), last(end),
 380          position(first), backstop(l_base), re(e), traits_inst(e.get_traits()),
 381          m_independent(false), next_count(&rep_obj), rep_obj(&next_count)
 382    {
 383       construct_init(e, f);
 384    }
 385
 386    bool match();
 387    bool find();
 388
 389    void setf(match_flag_type f)
 390    { m_match_flags |= f; }
 391    void unsetf(match_flag_type f)
 392    { m_match_flags &= ~f; }
 393
 394 private:
 395    void construct_init(const basic_regex<char_type, traits>& e, match_flag_type f);
 396
 397    bool find_imp();
 398    bool match_imp();
 399 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
 400    typedef bool (perl_matcher::*protected_proc_type)();
 401    bool protected_call(protected_proc_type);
 402 #endif
 403    void estimate_max_state_count(std::random_access_iterator_tag*);
 404    void estimate_max_state_count(void*);
 405    bool match_prefix();
 406    bool match_all_states();
 407
 408    // match procs, stored in s_match_vtable:
 409    bool match_startmark();
 410    bool match_endmark();
 411    bool match_literal();
 412    bool match_start_line();
 413    bool match_end_line();
 414    bool match_wild();
 415    bool match_match();
 416    bool match_word_boundary();
 417    bool match_within_word();
 418    bool match_word_start();
 419    bool match_word_end();
 420    bool match_buffer_start();
 421    bool match_buffer_end();
 422    bool match_backref();
 423    bool match_long_set();
 424    bool match_set();
 425    bool match_jump();
 426    bool match_alt();
 427    bool match_rep();
 428    bool match_combining();
 429    bool match_soft_buffer_end();
 430    bool match_restart_continue();
 431    bool match_long_set_repeat();
 432    bool match_set_repeat();
 433    bool match_char_repeat();
 434    bool match_dot_repeat_fast();
 435    bool match_dot_repeat_slow();
 436    bool match_dot_repeat_dispatch()
 437    {
 438       return ::boost::is_random_access_iterator<BidiIterator>::value ? match_dot_repeat_fast() : match_dot_repeat_slow();
 439    }
 440    bool match_backstep();
 441    bool match_assert_backref();
 442    bool match_toggle_case();
 443 #ifdef BOOST_REGEX_RECURSIVE
 444    bool backtrack_till_match(std::size_t count);
 445 #endif
 446    bool match_recursion();
 447    bool match_fail();
 448    bool match_accept();
 449    bool match_commit();
 450    bool match_then();
 451    bool skip_until_paren(int index, bool match = true);
 452
 453    // find procs stored in s_find_vtable:
 454    bool find_restart_any();
 455    bool find_restart_word();
 456    bool find_restart_line();
 457    bool find_restart_buf();
 458    bool find_restart_lit();
 459
 460 private:
 461    // final result structure to be filled in:
 462    match_results<BidiIterator, Allocator>& m_result;
 463    // temporary result for POSIX matches:
 464    scoped_ptr<match_results<BidiIterator, Allocator> > m_temp_match;
 465    // pointer to actual result structure to fill in:
 466    match_results<BidiIterator, Allocator>* m_presult;
 467    // start of sequence being searched:
 468    BidiIterator base;
 469    // end of sequence being searched:
 470    BidiIterator last;
 471    // current character being examined:
 472    BidiIterator position;
 473    // where to restart next search after failed match attempt:
 474    BidiIterator restart;
 475    // where the current search started from, acts as base for $` during grep:
 476    BidiIterator search_base;
 477    // how far we can go back when matching lookbehind:
 478    BidiIterator backstop;
 479    // the expression being examined:
 480    const basic_regex<char_type, traits>& re;
 481    // the expression's traits class:
 482    const ::boost::regex_traits_wrapper<traits>& traits_inst;
 483    // the next state in the machine being matched:
 484    const re_syntax_base* pstate;
 485    // matching flags in use:
 486    match_flag_type m_match_flags;
 487    // how many states we have examined so far:
 488    std::ptrdiff_t state_count;
 489    // max number of states to examine before giving up:
 490    std::ptrdiff_t max_state_count;
 491    // whether we should ignore case or not:
 492    bool icase;
 493    // set to true when (position == last), indicates that we may have a partial match:
 494    bool m_has_partial_match;
 495    // set to true whenever we get a match:
 496    bool m_has_found_match;
 497    // set to true whenever we're inside an independent sub-expression:
 498    bool m_independent;
 499    // the current repeat being examined:
 500    repeater_count<BidiIterator>* next_count;
 501    // the first repeat being examined (top of linked list):
 502    repeater_count<BidiIterator> rep_obj;
 503    // the mask to pass when matching word boundaries:
 504    typename traits::char_class_type m_word_mask;
 505    // the bitmask to use when determining whether a match_any matches a newline or not:
 506    unsigned char match_any_mask;
 507    // recursion information:
 508    std::vector<recursion_info<results_type> > recursion_stack;
 509 #ifdef BOOST_REGEX_RECURSIVE
 510    // Set to false by a (*COMMIT):
 511    bool m_can_backtrack;
 512    bool m_have_accept;
 513    bool m_have_then;
 514 #endif
 515 #ifdef BOOST_REGEX_NON_RECURSIVE
 516    //
 517    // additional members for non-recursive version:
 518    //
 519    typedef bool (self_type::*unwind_proc_type)(bool);
 520
 521    void extend_stack();
 522    bool unwind(bool);
 523    bool unwind_end(bool);
 524    bool unwind_paren(bool);
 525    bool unwind_recursion_stopper(bool);
 526    bool unwind_assertion(bool);
 527    bool unwind_alt(bool);
 528    bool unwind_repeater_counter(bool);
 529    bool unwind_extra_block(bool);
 530    bool unwind_greedy_single_repeat(bool);
 531    bool unwind_slow_dot_repeat(bool);
 532    bool unwind_fast_dot_repeat(bool);
 533    bool unwind_char_repeat(bool);
 534    bool unwind_short_set_repeat(bool);
 535    bool unwind_long_set_repeat(bool);
 536    bool unwind_non_greedy_repeat(bool);
 537    bool unwind_recursion(bool);
 538    bool unwind_recursion_pop(bool);
 539    bool unwind_commit(bool);
 540    bool unwind_then(bool);
 541    bool unwind_case(bool);
 542    void destroy_single_repeat();
 543    void push_matched_paren(int index, const sub_match<BidiIterator>& sub);
 544    void push_recursion_stopper();
 545    void push_assertion(const re_syntax_base* ps, bool positive);
 546    void push_alt(const re_syntax_base* ps);
 547    void push_repeater_count(int i, repeater_count<BidiIterator>** s);
 548    void push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id);
 549    void push_non_greedy_repeat(const re_syntax_base* ps);
 550    void push_recursion(int idx, const re_syntax_base* p, results_type* presults);
 551    void push_recursion_pop();
 552    void push_case_change(bool);
 553
 554    // pointer to base of stack:
 555    saved_state* m_stack_base;
 556    // pointer to current stack position:
 557    saved_state* m_backup_state;
 558    // how many memory blocks have we used up?:
 559    unsigned used_block_count;
 560    // determines what value to return when unwinding from recursion,
 561    // allows for mixed recursive/non-recursive algorithm:
 562    bool m_recursive_result;
 563    // We have unwound to a lookahead/lookbehind, used by COMMIT/PRUNE/SKIP:
 564    bool m_unwound_lookahead;
 565    // We have unwound to an alternative, used by THEN:
 566    bool m_unwound_alt;
 567    // We are unwinding a commit - used by independent subs to determine whether to stop there or carry on unwinding:
 568    //bool m_unwind_commit;
 569 #endif
 570
 571    // these operations aren't allowed, so are declared private,
 572    // bodies are provided to keep explicit-instantiation requests happy:
 573    perl_matcher& operator=(const perl_matcher&)
 574    {
 575       return *this;
 576    }
 577    perl_matcher(const perl_matcher& that)
 578       : m_result(that.m_result), re(that.re), traits_inst(that.traits_inst), rep_obj(0) {}
 579 };
 580
 581 #ifdef BOOST_MSVC
 582 #pragma warning(pop)
 583 #endif
 584
 585 } // namespace BOOST_REGEX_DETAIL_NS
 586
 587 #ifdef BOOST_MSVC
 588 #pragma warning(push)
 589 #pragma warning(disable: 4103)
 590 #endif
 591 #ifdef BOOST_HAS_ABI_HEADERS
 592 #  include BOOST_ABI_SUFFIX
 593 #endif
 594 #ifdef BOOST_MSVC
 595 #pragma warning(pop)
 596 #endif
 597
 598 } // namespace boost
 599
 600 #ifdef BOOST_MSVC
 601 #  pragma warning(pop)
 602 #endif
 603
 604 //
 605 // include the implementation of perl_matcher:
 606 //
 607 #ifdef BOOST_REGEX_RECURSIVE
 608 #include <boost/regex/v4/perl_matcher_recursive.hpp>
 609 #else
 610 #include <boost/regex/v4/perl_matcher_non_recursive.hpp>
 611 #endif
 612 // this one has to be last:
 613 #include <boost/regex/v4/perl_matcher_common.hpp>
 614
 615 #endif
 616