include/boost/regex/v5/perl_matcher.hpp

97.8% Lines (134/137) 62.1% List of functions (221/356)

[ ] prev/next file n p prev/next uncovered line

perl_matcher.hpp

f(x) Functions (356)

Function Calls Lines Blocks

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