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 re_detail{
  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) // 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 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1310)
  90 template <class C, class T, class A>
  91 inline int string_compare(const std::basic_string<C,T,A>& s, const C* p)
  92 {
  93    if(0 == *p)
  94    {
  95       if(s.empty() || ((s.size() == 1) && (s[0] == 0)))
  96          return 0;
  97    }
  98    return s.compare(p);
  99 }
 100 #endif
 101 #else
 102 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1310)
 103 template <class C, class T, class A>
 104 inline int string_compare(const std::basic_string<C,T,A>& s, const C* p)
 105 {
 106    if(0 == *p)
 107    {
 108       if(s.empty() || ((s.size() == 1) && (s[0] == 0)))
 109          return 0;
 110    }
 111    return s.compare(p);
 112 }
 113 #endif
 114 inline int string_compare(const std::string& s, const char* p)
 115 { return std::strcmp(s.c_str(), p); }
 116 # ifndef BOOST_NO_WREGEX
 117 inline int string_compare(const std::wstring& s, const wchar_t* p)
 118 { return std::wcscmp(s.c_str(), p); }
 119 #endif
 120 #endif
 121 template <class Seq, class C>
 122 inline int string_compare(const Seq& s, const C* p)
 123 {
 124    std::size_t i = 0;
 125    while((i < s.size()) && (p[i] == s[i]))
 126    {
 127       ++i;
 128    }
 129    return (i == s.size()) ? -p[i] : s[i] - p[i];
 130 }
 131 # define STR_COMP(s,p) string_compare(s,p)
 132
 133 template<class charT>
 134 inline const charT* re_skip_past_null(const charT* p)
 135 {
 136   while (*p != static_cast<charT>(0)) ++p;
 137   return ++p;
 138 }
 139
 140 template <class iterator, class charT, class traits_type, class char_classT>
 141 iterator BOOST_REGEX_CALL re_is_set_member(iterator next,
 142                           iterator last,
 143                           const re_set_long<char_classT>* set_,
 144                           const regex_data<charT, traits_type>& e, bool icase)
 145 {
 146    const charT* p = reinterpret_cast<const charT*>(set_+1);
 147    iterator ptr;
 148    unsigned int i;
 149    //bool icase = e.m_flags & regex_constants::icase;
 150
 151    if(next == last) return next;
 152
 153    typedef typename traits_type::string_type traits_string_type;
 154    const ::boost::regex_traits_wrapper<traits_type>& traits_inst = *(e.m_ptraits);
 155
 156    // dwa 9/13/00 suppress incorrect MSVC warning - it claims this is never
 157    // referenced
 158    (void)traits_inst;
 159
 160    // try and match a single character, could be a multi-character
 161    // collating element...
 162    for(i = 0; i < set_->csingles; ++i)
 163    {
 164       ptr = next;
 165       if(*p == static_cast<charT>(0))
 166       {
 167          // treat null string as special case:
 168          if(traits_inst.translate(*ptr, icase) != *p)
 169          {
 170             while(*p == static_cast<charT>(0))++p;
 171             continue;
 172          }
 173          return set_->isnot ? next : (ptr == next) ? ++next : ptr;
 174       }
 175       else
 176       {
 177          while(*p && (ptr != last))
 178          {
 179             if(traits_inst.translate(*ptr, icase) != *p)
 180                break;
 181             ++p;
 182             ++ptr;
 183          }
 184
 185          if(*p == static_cast<charT>(0)) // if null we've matched
 186             return set_->isnot ? next : (ptr == next) ? ++next : ptr;
 187
 188          p = re_skip_past_null(p);     // skip null
 189       }
 190    }
 191
 192    charT col = traits_inst.translate(*next, icase);
 193
 194
 195    if(set_->cranges || set_->cequivalents)
 196    {
 197       traits_string_type s1;
 198       //
 199       // try and match a range, NB only a single character can match
 200       if(set_->cranges)
 201       {
 202          if((e.m_flags & regex_constants::collate) == 0)
 203             s1.assign(1, col);
 204          else
 205          {
 206             charT a[2] = { col, charT(0), };
 207             s1 = traits_inst.transform(a, a + 1);
 208          }
 209          for(i = 0; i < set_->cranges; ++i)
 210          {
 211             if(STR_COMP(s1, p) >= 0)
 212             {
 213                do{ ++p; }while(*p);
 214                ++p;
 215                if(STR_COMP(s1, p) <= 0)
 216                   return set_->isnot ? next : ++next;
 217             }
 218             else
 219             {
 220                // skip first string
 221                do{ ++p; }while(*p);
 222                ++p;
 223             }
 224             // skip second string
 225             do{ ++p; }while(*p);
 226             ++p;
 227          }
 228       }
 229       //
 230       // try and match an equivalence class, NB only a single character can match
 231       if(set_->cequivalents)
 232       {
 233          charT a[2] = { col, charT(0), };
 234          s1 = traits_inst.transform_primary(a, a +1);
 235          for(i = 0; i < set_->cequivalents; ++i)
 236          {
 237             if(STR_COMP(s1, p) == 0)
 238                return set_->isnot ? next : ++next;
 239             // skip string
 240             do{ ++p; }while(*p);
 241             ++p;
 242          }
 243       }
 244    }
 245    if(traits_inst.isctype(col, set_->cclasses) == true)
 246       return set_->isnot ? next : ++next;
 247    if((set_->cnclasses != 0) && (traits_inst.isctype(col, set_->cnclasses) == false))
 248       return set_->isnot ? next : ++next;
 249    return set_->isnot ? ++next : next;
 250 }
 251
 252 template <class BidiIterator>
 253 class repeater_count
 254 {
 255    repeater_count** stack;
 256    repeater_count* next;
 257    int state_id;
 258    std::size_t count;        // the number of iterations so far
 259    BidiIterator start_pos;   // where the last repeat started
 260 public:
 261    repeater_count(repeater_count** s)
 262    {
 263       stack = s;
 264       next = 0;
 265       state_id = -1;
 266       count = 0;
 267    }
 268    repeater_count(int i, repeater_count** s, BidiIterator start)
 269       : start_pos(start)
 270    {
 271       state_id = i;
 272       stack = s;
 273       next = *stack;
 274       *stack = this;
 275       if(state_id > next->state_id)
 276          count = 0;
 277       else
 278       {
 279          repeater_count* p = next;
 280          while(p->state_id != state_id)
 281             p = p->next;
 282          count = p->count;
 283          start_pos = p->start_pos;
 284       }
 285    }
 286    ~repeater_count()
 287    {
 288       *stack = next;
 289    }
 290    std::size_t get_count() { return count; }
 291    int get_id() { return state_id; }
 292    std::size_t operator++() { return ++count; }
 293    bool check_null_repeat(const BidiIterator& pos, std::size_t max)
 294    {
 295       // this is called when we are about to start a new repeat,
 296       // if the last one was NULL move our count to max,
 297       // otherwise save the current position.
 298       bool result = (count == 0) ? false : (pos == start_pos);
 299       if(result)
 300          count = max;
 301       else
 302          start_pos = pos;
 303       return result;
 304    }
 305 };
 306
 307 struct saved_state;
 308
 309 enum saved_state_type
 310 {
 311    saved_type_end = 0,
 312    saved_type_paren = 1,
 313    saved_type_recurse = 2,
 314    saved_type_assertion = 3,
 315    saved_state_alt = 4,
 316    saved_state_repeater_count = 5,
 317    saved_state_extra_block = 6,
 318    saved_state_greedy_single_repeat = 7,
 319    saved_state_rep_slow_dot = 8,
 320    saved_state_rep_fast_dot = 9,
 321    saved_state_rep_char = 10,
 322    saved_state_rep_short_set = 11,
 323    saved_state_rep_long_set = 12,
 324    saved_state_non_greedy_long_repeat = 13,
 325    saved_state_count = 14
 326 };
 327
 328 #ifdef BOOST_MSVC
 329 #pragma warning(push)
 330 #pragma warning(disable : 4251 4231 4660)
 331 #endif
 332
 333 template <class BidiIterator, class Allocator, class traits>
 334 class perl_matcher
 335 {
 336 public:
 337    typedef typename traits::char_type char_type;
 338    typedef perl_matcher<BidiIterator, Allocator, traits> self_type;
 339    typedef bool (self_type::*matcher_proc_type)(void);
 340    typedef std::size_t traits_size_type;
 341    typedef typename is_byte<char_type>::width_type width_type;
 342    typedef typename regex_iterator_traits<BidiIterator>::difference_type difference_type;
 343
 344    perl_matcher(BidiIterator first, BidiIterator end,
 345       match_results<BidiIterator, Allocator>& what,
 346       const basic_regex<char_type, traits>& e,
 347       match_flag_type f,
 348       BidiIterator l_base)
 349       :  m_result(what), base(first), last(end),
 350          position(first), backstop(l_base), re(e), traits_inst(e.get_traits()),
 351          m_independent(false), next_count(&rep_obj), rep_obj(&next_count)
 352    {
 353       construct_init(e, f);
 354    }
 355
 356    bool match();
 357    bool find();
 358
 359    void setf(match_flag_type f)
 360    { m_match_flags |= f; }
 361    void unsetf(match_flag_type f)
 362    { m_match_flags &= ~f; }
 363
 364 private:
 365    void construct_init(const basic_regex<char_type, traits>& e, match_flag_type f);
 366
 367    bool find_imp();
 368    bool match_imp();
 369 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
 370    typedef bool (perl_matcher::*protected_proc_type)();
 371    bool protected_call(protected_proc_type);
 372 #endif
 373    void estimate_max_state_count(std::random_access_iterator_tag*);
 374    void estimate_max_state_count(void*);
 375    bool match_prefix();
 376    bool match_all_states();
 377
 378    // match procs, stored in s_match_vtable:
 379    bool match_startmark();
 380    bool match_endmark();
 381    bool match_literal();
 382    bool match_start_line();
 383    bool match_end_line();
 384    bool match_wild();
 385    bool match_match();
 386    bool match_word_boundary();
 387    bool match_within_word();
 388    bool match_word_start();
 389    bool match_word_end();
 390    bool match_buffer_start();
 391    bool match_buffer_end();
 392    bool match_backref();
 393    bool match_long_set();
 394    bool match_set();
 395    bool match_jump();
 396    bool match_alt();
 397    bool match_rep();
 398    bool match_combining();
 399    bool match_soft_buffer_end();
 400    bool match_restart_continue();
 401    bool match_long_set_repeat();
 402    bool match_set_repeat();
 403    bool match_char_repeat();
 404    bool match_dot_repeat_fast();
 405    bool match_dot_repeat_slow();
 406    bool match_backstep();
 407    bool match_assert_backref();
 408    bool match_toggle_case();
 409 #ifdef BOOST_REGEX_RECURSIVE
 410    bool backtrack_till_match(std::size_t count);
 411 #endif
 412
 413    // find procs stored in s_find_vtable:
 414    bool find_restart_any();
 415    bool find_restart_word();
 416    bool find_restart_line();
 417    bool find_restart_buf();
 418    bool find_restart_lit();
 419
 420 private:
 421    // final result structure to be filled in:
 422    match_results<BidiIterator, Allocator>& m_result;
 423    // temporary result for POSIX matches:
 424    scoped_ptr<match_results<BidiIterator, Allocator> > m_temp_match;
 425    // pointer to actual result structure to fill in:
 426    match_results<BidiIterator, Allocator>* m_presult;
 427    // start of sequence being searched:
 428    BidiIterator base;
 429    // end of sequence being searched:
 430    BidiIterator last;
 431    // current character being examined:
 432    BidiIterator position;
 433    // where to restart next search after failed match attempt:
 434    BidiIterator restart;
 435    // where the current search started from, acts as base for $` during grep:
 436    BidiIterator search_base;
 437    // how far we can go back when matching lookbehind:
 438    BidiIterator backstop;
 439    // the expression being examined:
 440    const basic_regex<char_type, traits>& re;
 441    // the expression's traits class:
 442    const ::boost::regex_traits_wrapper<traits>& traits_inst;
 443    // the next state in the machine being matched:
 444    const re_syntax_base* pstate;
 445    // matching flags in use:
 446    match_flag_type m_match_flags;
 447    // how many states we have examined so far:
 448    boost::uintmax_t state_count;
 449    // max number of states to examine before giving up:
 450    boost::uintmax_t max_state_count;
 451    // whether we should ignore case or not:
 452    bool icase;
 453    // set to true when (position == last), indicates that we may have a partial match:
 454    bool m_has_partial_match;
 455    // set to true whenever we get a match:
 456    bool m_has_found_match;
 457    // set to true whenever we're inside an independent sub-expression:
 458    bool m_independent;
 459    // the current repeat being examined:
 460    repeater_count<BidiIterator>* next_count;
 461    // the first repeat being examined (top of linked list):
 462    repeater_count<BidiIterator> rep_obj;
 463    // the mask to pass when matching word boundaries:
 464    typename traits::char_class_type m_word_mask;
 465    // the bitmask to use when determining whether a match_any matches a newline or not:
 466    unsigned char match_any_mask;
 467
 468 #ifdef BOOST_REGEX_NON_RECURSIVE
 469    //
 470    // additional members for non-recursive version:
 471    //
 472    typedef bool (self_type::*unwind_proc_type)(bool);
 473
 474    void extend_stack();
 475    bool unwind(bool);
 476    bool unwind_end(bool);
 477    bool unwind_paren(bool);
 478    bool unwind_recursion_stopper(bool);
 479    bool unwind_assertion(bool);
 480    bool unwind_alt(bool);
 481    bool unwind_repeater_counter(bool);
 482    bool unwind_extra_block(bool);
 483    bool unwind_greedy_single_repeat(bool);
 484    bool unwind_slow_dot_repeat(bool);
 485    bool unwind_fast_dot_repeat(bool);
 486    bool unwind_char_repeat(bool);
 487    bool unwind_short_set_repeat(bool);
 488    bool unwind_long_set_repeat(bool);
 489    bool unwind_non_greedy_repeat(bool);
 490    void destroy_single_repeat();
 491    void push_matched_paren(int index, const sub_match<BidiIterator>& sub);
 492    void push_recursion_stopper();
 493    void push_assertion(const re_syntax_base* ps, bool positive);
 494    void push_alt(const re_syntax_base* ps);
 495    void push_repeater_count(int i, repeater_count<BidiIterator>** s);
 496    void push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id);
 497    void push_non_greedy_repeat(const re_syntax_base* ps);
 498
 499
 500    // pointer to base of stack:
 501    saved_state* m_stack_base;
 502    // pointer to current stack position:
 503    saved_state* m_backup_state;
 504    // determines what value to return when unwinding from recursion,
 505    // allows for mixed recursive/non-recursive algorithm:
 506    bool m_recursive_result;
 507    // how many memory blocks have we used up?:
 508    unsigned used_block_count;
 509 #endif
 510
 511    // these operations aren't allowed, so are declared private,
 512    // bodies are provided to keep explicit-instantiation requests happy:
 513    perl_matcher& operator=(const perl_matcher&)
 514    {
 515       return *this;
 516    }
 517    perl_matcher(const perl_matcher& that)
 518       : m_result(that.m_result), re(that.re), traits_inst(that.traits_inst), rep_obj(0) {}
 519 };
 520
 521 #ifdef BOOST_MSVC
 522 #pragma warning(pop)
 523 #endif
 524
 525 } // namespace re_detail
 526
 527 #ifdef BOOST_MSVC
 528 #pragma warning(push)
 529 #pragma warning(disable: 4103)
 530 #endif
 531 #ifdef BOOST_HAS_ABI_HEADERS
 532 #  include BOOST_ABI_SUFFIX
 533 #endif
 534 #ifdef BOOST_MSVC
 535 #pragma warning(pop)
 536 #endif
 537
 538 } // namespace boost
 539
 540 #ifdef BOOST_MSVC
 541 #  pragma warning(pop)
 542 #endif
 543
 544 //
 545 // include the implementation of perl_matcher:
 546 //
 547 #ifdef BOOST_REGEX_RECURSIVE
 548 #include <boost/regex/v4/perl_matcher_recursive.hpp>
 549 #else
 550 #include <boost/regex/v4/perl_matcher_non_recursive.hpp>
 551 #endif
 552 // this one has to be last:
 553 #include <boost/regex/v4/perl_matcher_common.hpp>
 554
 555 #endif
 556