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>
can_start(charT c,const unsigned char * map,unsigned char mask)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 }
can_start(char c,const unsigned char * map,unsigned char mask)48 inline bool can_start(char c, const unsigned char* map, unsigned char mask)
49 {
50 return map[(unsigned char)c] & mask;
51 }
can_start(signed char c,const unsigned char * map,unsigned char mask)52 inline bool can_start(signed char c, const unsigned char* map, unsigned char mask)
53 {
54 return map[(unsigned char)c] & mask;
55 }
can_start(unsigned char c,const unsigned char * map,unsigned char mask)56 inline bool can_start(unsigned char c, const unsigned char* map, unsigned char mask)
57 {
58 return map[c] & mask;
59 }
can_start(unsigned short c,const unsigned char * map,unsigned char mask)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)
can_start(wchar_t c,const unsigned char * map,unsigned char mask)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)
can_start(unsigned int c,const unsigned char * map,unsigned char mask)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>
string_compare(const std::basic_string<C,T,A> & s,const C * p)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>
string_compare(const std::basic_string<C,T,A> & s,const C * p)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
string_compare(const std::string & s,const char * p)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
string_compare(const std::wstring & s,const wchar_t * p)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>
string_compare(const Seq & s,const C * p)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>
re_skip_past_null(const charT * p)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:
repeater_count(repeater_count ** s)261 repeater_count(repeater_count** s)
262 {
263 stack = s;
264 next = 0;
265 state_id = -1;
266 count = 0;
267 }
repeater_count(int i,repeater_count ** s,BidiIterator start)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 && (p->state_id != state_id))
281 p = p->next;
282 if(p)
283 {
284 count = p->count;
285 start_pos = p->start_pos;
286 }
287 else
288 count = 0;
289 }
290 }
~repeater_count()291 ~repeater_count()
292 {
293 if(next)
294 *stack = next;
295 }
get_count()296 std::size_t get_count() { return count; }
get_id()297 int get_id() { return state_id; }
operator ++()298 std::size_t operator++() { return ++count; }
check_null_repeat(const BidiIterator & pos,std::size_t max)299 bool check_null_repeat(const BidiIterator& pos, std::size_t max)
300 {
301 // this is called when we are about to start a new repeat,
302 // if the last one was NULL move our count to max,
303 // otherwise save the current position.
304 bool result = (count == 0) ? false : (pos == start_pos);
305 if(result)
306 count = max;
307 else
308 start_pos = pos;
309 return result;
310 }
311 };
312
313 struct saved_state;
314
315 enum saved_state_type
316 {
317 saved_type_end = 0,
318 saved_type_paren = 1,
319 saved_type_recurse = 2,
320 saved_type_assertion = 3,
321 saved_state_alt = 4,
322 saved_state_repeater_count = 5,
323 saved_state_extra_block = 6,
324 saved_state_greedy_single_repeat = 7,
325 saved_state_rep_slow_dot = 8,
326 saved_state_rep_fast_dot = 9,
327 saved_state_rep_char = 10,
328 saved_state_rep_short_set = 11,
329 saved_state_rep_long_set = 12,
330 saved_state_non_greedy_long_repeat = 13,
331 saved_state_count = 14
332 };
333
334 template <class Results>
335 struct recursion_info
336 {
337 typedef typename Results::value_type value_type;
338 typedef typename value_type::iterator iterator;
339 int idx;
340 const re_syntax_base* preturn_address;
341 Results results;
342 repeater_count<iterator>* repeater_stack;
343 };
344
345 #ifdef BOOST_MSVC
346 #pragma warning(push)
347 #pragma warning(disable : 4251 4231 4660)
348 #endif
349
350 template <class BidiIterator, class Allocator, class traits>
351 class perl_matcher
352 {
353 public:
354 typedef typename traits::char_type char_type;
355 typedef perl_matcher<BidiIterator, Allocator, traits> self_type;
356 typedef bool (self_type::*matcher_proc_type)(void);
357 typedef std::size_t traits_size_type;
358 typedef typename is_byte<char_type>::width_type width_type;
359 typedef typename regex_iterator_traits<BidiIterator>::difference_type difference_type;
360 typedef match_results<BidiIterator, Allocator> results_type;
361
perl_matcher(BidiIterator first,BidiIterator end,match_results<BidiIterator,Allocator> & what,const basic_regex<char_type,traits> & e,match_flag_type f,BidiIterator l_base)362 perl_matcher(BidiIterator first, BidiIterator end,
363 match_results<BidiIterator, Allocator>& what,
364 const basic_regex<char_type, traits>& e,
365 match_flag_type f,
366 BidiIterator l_base)
367 : m_result(what), base(first), last(end),
368 position(first), backstop(l_base), re(e), traits_inst(e.get_traits()),
369 m_independent(false), next_count(&rep_obj), rep_obj(&next_count)
370 {
371 construct_init(e, f);
372 }
373
374 bool match();
375 bool find();
376
setf(match_flag_type f)377 void setf(match_flag_type f)
378 { m_match_flags |= f; }
unsetf(match_flag_type f)379 void unsetf(match_flag_type f)
380 { m_match_flags &= ~f; }
381
382 private:
383 void construct_init(const basic_regex<char_type, traits>& e, match_flag_type f);
384
385 bool find_imp();
386 bool match_imp();
387 #ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
388 typedef bool (perl_matcher::*protected_proc_type)();
389 bool protected_call(protected_proc_type);
390 #endif
391 void estimate_max_state_count(std::random_access_iterator_tag*);
392 void estimate_max_state_count(void*);
393 bool match_prefix();
394 bool match_all_states();
395
396 // match procs, stored in s_match_vtable:
397 bool match_startmark();
398 bool match_endmark();
399 bool match_literal();
400 bool match_start_line();
401 bool match_end_line();
402 bool match_wild();
403 bool match_match();
404 bool match_word_boundary();
405 bool match_within_word();
406 bool match_word_start();
407 bool match_word_end();
408 bool match_buffer_start();
409 bool match_buffer_end();
410 bool match_backref();
411 bool match_long_set();
412 bool match_set();
413 bool match_jump();
414 bool match_alt();
415 bool match_rep();
416 bool match_combining();
417 bool match_soft_buffer_end();
418 bool match_restart_continue();
419 bool match_long_set_repeat();
420 bool match_set_repeat();
421 bool match_char_repeat();
422 bool match_dot_repeat_fast();
423 bool match_dot_repeat_slow();
match_dot_repeat_dispatch()424 bool match_dot_repeat_dispatch()
425 {
426 return ::boost::is_random_access_iterator<BidiIterator>::value ? match_dot_repeat_fast() : match_dot_repeat_slow();
427 }
428 bool match_backstep();
429 bool match_assert_backref();
430 bool match_toggle_case();
431 #ifdef BOOST_REGEX_RECURSIVE
432 bool backtrack_till_match(std::size_t count);
433 #endif
434 bool match_recursion();
435
436 // find procs stored in s_find_vtable:
437 bool find_restart_any();
438 bool find_restart_word();
439 bool find_restart_line();
440 bool find_restart_buf();
441 bool find_restart_lit();
442
443 private:
444 // final result structure to be filled in:
445 match_results<BidiIterator, Allocator>& m_result;
446 // temporary result for POSIX matches:
447 scoped_ptr<match_results<BidiIterator, Allocator> > m_temp_match;
448 // pointer to actual result structure to fill in:
449 match_results<BidiIterator, Allocator>* m_presult;
450 // start of sequence being searched:
451 BidiIterator base;
452 // end of sequence being searched:
453 BidiIterator last;
454 // current character being examined:
455 BidiIterator position;
456 // where to restart next search after failed match attempt:
457 BidiIterator restart;
458 // where the current search started from, acts as base for $` during grep:
459 BidiIterator search_base;
460 // how far we can go back when matching lookbehind:
461 BidiIterator backstop;
462 // the expression being examined:
463 const basic_regex<char_type, traits>& re;
464 // the expression's traits class:
465 const ::boost::regex_traits_wrapper<traits>& traits_inst;
466 // the next state in the machine being matched:
467 const re_syntax_base* pstate;
468 // matching flags in use:
469 match_flag_type m_match_flags;
470 // how many states we have examined so far:
471 std::ptrdiff_t state_count;
472 // max number of states to examine before giving up:
473 std::ptrdiff_t max_state_count;
474 // whether we should ignore case or not:
475 bool icase;
476 // set to true when (position == last), indicates that we may have a partial match:
477 bool m_has_partial_match;
478 // set to true whenever we get a match:
479 bool m_has_found_match;
480 // set to true whenever we're inside an independent sub-expression:
481 bool m_independent;
482 // the current repeat being examined:
483 repeater_count<BidiIterator>* next_count;
484 // the first repeat being examined (top of linked list):
485 repeater_count<BidiIterator> rep_obj;
486 // the mask to pass when matching word boundaries:
487 typename traits::char_class_type m_word_mask;
488 // the bitmask to use when determining whether a match_any matches a newline or not:
489 unsigned char match_any_mask;
490 // recursion information:
491 std::vector<recursion_info<results_type> > recursion_stack;
492
493 #ifdef BOOST_REGEX_NON_RECURSIVE
494 //
495 // additional members for non-recursive version:
496 //
497 typedef bool (self_type::*unwind_proc_type)(bool);
498
499 void extend_stack();
500 bool unwind(bool);
501 bool unwind_end(bool);
502 bool unwind_paren(bool);
503 bool unwind_recursion_stopper(bool);
504 bool unwind_assertion(bool);
505 bool unwind_alt(bool);
506 bool unwind_repeater_counter(bool);
507 bool unwind_extra_block(bool);
508 bool unwind_greedy_single_repeat(bool);
509 bool unwind_slow_dot_repeat(bool);
510 bool unwind_fast_dot_repeat(bool);
511 bool unwind_char_repeat(bool);
512 bool unwind_short_set_repeat(bool);
513 bool unwind_long_set_repeat(bool);
514 bool unwind_non_greedy_repeat(bool);
515 bool unwind_recursion(bool);
516 bool unwind_recursion_pop(bool);
517 void destroy_single_repeat();
518 void push_matched_paren(int index, const sub_match<BidiIterator>& sub);
519 void push_recursion_stopper();
520 void push_assertion(const re_syntax_base* ps, bool positive);
521 void push_alt(const re_syntax_base* ps);
522 void push_repeater_count(int i, repeater_count<BidiIterator>** s);
523 void push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id);
524 void push_non_greedy_repeat(const re_syntax_base* ps);
525 void push_recursion(int idx, const re_syntax_base* p, results_type* presults);
526 void push_recursion_pop();
527
528 // pointer to base of stack:
529 saved_state* m_stack_base;
530 // pointer to current stack position:
531 saved_state* m_backup_state;
532 // determines what value to return when unwinding from recursion,
533 // allows for mixed recursive/non-recursive algorithm:
534 bool m_recursive_result;
535 // how many memory blocks have we used up?:
536 unsigned used_block_count;
537 #endif
538
539 // these operations aren't allowed, so are declared private,
540 // bodies are provided to keep explicit-instantiation requests happy:
operator =(const perl_matcher &)541 perl_matcher& operator=(const perl_matcher&)
542 {
543 return *this;
544 }
perl_matcher(const perl_matcher & that)545 perl_matcher(const perl_matcher& that)
546 : m_result(that.m_result), re(that.re), traits_inst(that.traits_inst), rep_obj(0) {}
547 };
548
549 #ifdef BOOST_MSVC
550 #pragma warning(pop)
551 #endif
552
553 } // namespace re_detail
554
555 #ifdef BOOST_MSVC
556 #pragma warning(push)
557 #pragma warning(disable: 4103)
558 #endif
559 #ifdef BOOST_HAS_ABI_HEADERS
560 # include BOOST_ABI_SUFFIX
561 #endif
562 #ifdef BOOST_MSVC
563 #pragma warning(pop)
564 #endif
565
566 } // namespace boost
567
568 #ifdef BOOST_MSVC
569 # pragma warning(pop)
570 #endif
571
572 //
573 // include the implementation of perl_matcher:
574 //
575 #ifdef BOOST_REGEX_RECURSIVE
576 #include <boost/regex/v4/perl_matcher_recursive.hpp>
577 #else
578 #include <boost/regex/v4/perl_matcher_non_recursive.hpp>
579 #endif
580 // this one has to be last:
581 #include <boost/regex/v4/perl_matcher_common.hpp>
582
583 #endif
584
585