include/boost/regex/v5/basic_regex_creator.hpp

98.4% Lines (793/806) 89.2% List of functions (331/372)

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

basic_regex_creator.hpp

f(x) Functions (372)

Function Calls Lines Blocks

Line	Hits	Source Code
1		/*
2		*
3		* Copyright (c) 2004
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		/*
13		* LOCATION: see http://www.boost.org for most recent version.
14		* FILE basic_regex_creator.cpp
15		* VERSION see <boost/version.hpp>
16		* DESCRIPTION: Declares template class basic_regex_creator which fills in
17		* the data members of a regex_data object.
18		*/
19
20		#ifndef BOOST_REGEX_V5_BASIC_REGEX_CREATOR_HPP
21		#define BOOST_REGEX_V5_BASIC_REGEX_CREATOR_HPP
22
23		#ifdef BOOST_REGEX_MSVC
24		# pragma warning(push)
25		#pragma warning(disable:4459)
26		#if BOOST_REGEX_MSVC < 1910
27		#pragma warning(disable:4800)
28		#endif
29		#endif
30
31		#include <boost/regex/v5/basic_regex.hpp>
32
33		#ifndef BOOST_REGEX_AS_MODULE
34		#include <vector>
35		#include <set>
36		#endif
37
38		namespace boost{
39
40		namespace BOOST_REGEX_DETAIL_NS{
41
42		template <class charT>
43		struct digraph : public std::pair<charT, charT>
44		{
45	919583x	digraph() : std::pair<charT, charT>(charT(0), charT(0)){}
46	902739x	digraph(charT c1) : std::pair<charT, charT>(c1, charT(0)){}
47		digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
48		{}
49	1122004x	digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
50	895563x	digraph<charT>& operator=(const digraph<charT>&) = default;
51		template <class Seq>
52		digraph(const Seq& s) : std::pair<charT, charT>()
53		{
54		BOOST_REGEX_ASSERT(s.size() <= 2);
55		BOOST_REGEX_ASSERT(s.size());
56		this->first = s[0];
57		this->second = (s.size() > 1) ? s[1] : 0;
58		}
59		};
60
61		template <class charT, class traits>
62		class basic_char_set
63		{
64		public:
65		typedef digraph<charT> digraph_type;
66		typedef typename traits::string_type string_type;
67		typedef typename traits::char_class_type m_type;
68
69	332044x	basic_char_set()
70	332044x	{
71	332044x	m_negate = false;
72	332044x	m_has_digraphs = false;
73	332044x	m_classes = 0;
74	332044x	m_negated_classes = 0;
75	332044x	m_empty = true;
76	332044x	}
77
78	656549x	void add_single(const digraph_type& s)
79		{
80	656549x	m_singles.insert(s);
81	656549x	if(s.second)
82	13368x	m_has_digraphs = true;
83	656549x	m_empty = false;
84	656549x	}
85	135199x	void add_range(const digraph_type& first, const digraph_type& end)
86		{
87	135199x	m_ranges.push_back(first);
88	135199x	m_ranges.push_back(end);
89	135199x	if(first.second)
90		{
91	2352x	m_has_digraphs = true;
92	2352x	add_single(first);
93		}
94	135199x	if(end.second)
95		{
96	1200x	m_has_digraphs = true;
97	1200x	add_single(end);
98		}
99	135199x	m_empty = false;
100	135199x	}
101	95851x	void add_class(m_type m)
102		{
103	95851x	m_classes \|= m;
104	95851x	m_empty = false;
105	95851x	}
106	1800x	void add_negated_class(m_type m)
107		{
108	1800x	m_negated_classes \|= m;
109	1800x	m_empty = false;
110	1800x	}
111	1312x	void add_equivalent(const digraph_type& s)
112		{
113	1312x	m_equivalents.insert(s);
114	1312x	if(s.second)
115		{
116	348x	m_has_digraphs = true;
117	348x	add_single(s);
118		}
119	1312x	m_empty = false;
120	1312x	}
121	136210x	void negate()
122		{
123	136210x	m_negate = true;
124		//m_empty = false;
125	136210x	}
126
127		//
128		// accessor functions:
129		//
130	478859x	bool has_digraphs()const
131		{
132	478859x	return m_has_digraphs;
133		}
134	324508x	bool is_negated()const
135		{
136	324508x	return m_negate;
137		}
138		typedef typename std::vector<digraph_type>::const_iterator list_iterator;
139		typedef typename std::set<digraph_type>::const_iterator set_iterator;
140	478859x	set_iterator singles_begin()const
141		{
142	478859x	return m_singles.begin();
143		}
144	478859x	set_iterator singles_end()const
145		{
146	478859x	return m_singles.end();
147		}
148	478859x	list_iterator ranges_begin()const
149		{
150	478859x	return m_ranges.begin();
151		}
152	478859x	list_iterator ranges_end()const
153		{
154	478859x	return m_ranges.end();
155		}
156	478331x	set_iterator equivalents_begin()const
157		{
158	478331x	return m_equivalents.begin();
159		}
160	478331x	set_iterator equivalents_end()const
161		{
162	478331x	return m_equivalents.end();
163		}
164	324412x	m_type classes()const
165		{
166	324412x	return m_classes;
167		}
168	324412x	m_type negated_classes()const
169		{
170	324412x	return m_negated_classes;
171		}
172	6186x	bool empty()const
173		{
174	6186x	return m_empty;
175		}
176		private:
177		std::set<digraph_type> m_singles; // a list of single characters to match
178		std::vector<digraph_type> m_ranges; // a list of end points of our ranges
179		bool m_negate; // true if the set is to be negated
180		bool m_has_digraphs; // true if we have digraphs present
181		m_type m_classes; // character classes to match
182		m_type m_negated_classes; // negated character classes to match
183		bool m_empty; // whether we've added anything yet
184		std::set<digraph_type> m_equivalents; // a list of equivalence classes
185		};
186
187		template <class charT, class traits>
188		class basic_regex_creator
189		{
190		public:
191		basic_regex_creator(regex_data<charT, traits>* data);
192	7913450x	std::ptrdiff_t getoffset(void* addr)
193		{
194	7913450x	return getoffset(addr, m_pdata->m_data.data());
195		}
196	7913450x	std::ptrdiff_t getoffset(const void* addr, const void* base)
197		{
198	7913450x	return static_cast<const char>(addr) - static_cast<const char>(base);
199		}
200	2027743x	re_syntax_base* getaddress(std::ptrdiff_t off)
201		{
202	2027743x	return getaddress(off, m_pdata->m_data.data());
203		}
204	7716064x	re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
205		{
206	7716064x	return static_cast<re_syntax_base>(static_cast<void>(static_cast<char*>(base) + off));
207		}
208	408235x	void init(unsigned l_flags)
209		{
210	408235x	m_pdata->m_flags = l_flags;
211	408235x	m_icase = l_flags & regex_constants::icase;
212	408235x	}
213	8666094x	regbase::flag_type flags()
214		{
215	8666094x	return m_pdata->m_flags;
216		}
217	946662x	void flags(regbase::flag_type f)
218		{
219	946662x	m_pdata->m_flags = f;
220	946662x	if(m_icase != static_cast<bool>(f & regbase::icase))
221		{
222	42037x	m_icase = static_cast<bool>(f & regbase::icase);
223		}
224	946662x	}
225		re_syntax_base* append_state(syntax_element_type t, std::size_t s);
226	486497x	re_syntax_base* append_state(syntax_element_type t) { return append_state(t, sizeof(re_syntax_base)); }
227		re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s);
228		re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t) { return insert_state(pos, t, sizeof(re_syntax_base)); }
229		re_literal* append_literal(charT c);
230		re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
231		re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, std::integral_constant<bool, false>*);
232		re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, std::integral_constant<bool, true>*);
233		void finalize(const charT* p1, const charT* p2);
234		protected:
235		regex_data<charT, traits>* m_pdata; // pointer to the basic_regex_data struct we are filling in
236		const ::boost::regex_traits_wrapper<traits>&
237		m_traits; // convenience reference to traits class
238		re_syntax_base* m_last_state; // the last state we added
239		bool m_icase; // true for case insensitive matches
240		unsigned m_repeater_id; // the state_id of the next repeater
241		bool m_has_backrefs; // true if there are actually any backrefs
242		std::uintmax_t m_bad_repeats; // bitmask of repeats we can't deduce a startmap for;
243		bool m_has_recursions; // set when we have recursive expressions to fixup
244		std::vector<unsigned char> m_recursion_checks; // notes which recursions we've followed while analysing this expression
245		typename traits::char_class_type m_word_mask; // mask used to determine if a character is a word character
246		typename traits::char_class_type m_mask_space; // mask used to determine if a character is a word character
247		typename traits::char_class_type m_lower_mask; // mask used to determine if a character is a lowercase character
248		typename traits::char_class_type m_upper_mask; // mask used to determine if a character is an uppercase character
249		typename traits::char_class_type m_alpha_mask; // mask used to determine if a character is an alphabetic character
250		private:
251		basic_regex_creator& operator=(const basic_regex_creator&);
252		basic_regex_creator(const basic_regex_creator&);
253
254		void fixup_pointers(re_syntax_base* state);
255		void fixup_recursions(re_syntax_base* state);
256		void create_startmaps(re_syntax_base* state);
257		int calculate_backstep(re_syntax_base* state);
258		void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask, unsigned recursion_count = 0);
259		unsigned get_restart_type(re_syntax_base* state);
260		void set_all_masks(unsigned char* bits, unsigned char);
261		bool is_bad_repeat(re_syntax_base* pt);
262		void set_bad_repeat(re_syntax_base* pt);
263		syntax_element_type get_repeat_type(re_syntax_base* state);
264		void probe_leading_repeat(re_syntax_base* state);
265		};
266
267		template <class charT, class traits>
268	408235x	basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
269	408235x	: m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_icase(false), m_repeater_id(0),
270	408235x	m_has_backrefs(false), m_bad_repeats(0), m_has_recursions(false), m_word_mask(0), m_mask_space(0), m_lower_mask(0), m_upper_mask(0), m_alpha_mask(0)
271		{
272	408235x	m_pdata->m_data.clear();
273	408235x	m_pdata->m_status = ::boost::regex_constants::error_ok;
274		static const charT w = 'w';
275		static const charT s = 's';
276		static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
277		static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
278		static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
279	408235x	m_word_mask = m_traits.lookup_classname(&w, &w +1);
280	408235x	m_mask_space = m_traits.lookup_classname(&s, &s +1);
281	408235x	m_lower_mask = m_traits.lookup_classname(l, l + 5);
282	408235x	m_upper_mask = m_traits.lookup_classname(u, u + 5);
283	408235x	m_alpha_mask = m_traits.lookup_classname(a, a + 5);
284	408235x	m_pdata->m_word_mask = m_word_mask;
285	408235x	BOOST_REGEX_ASSERT(m_word_mask != 0);
286	408235x	BOOST_REGEX_ASSERT(m_mask_space != 0);
287	408235x	BOOST_REGEX_ASSERT(m_lower_mask != 0);
288	408235x	BOOST_REGEX_ASSERT(m_upper_mask != 0);
289	408235x	BOOST_REGEX_ASSERT(m_alpha_mask != 0);
290	408235x	}
291
292		template <class charT, class traits>
293	4068295x	re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
294		{
295		// if the state is a backref then make a note of it:
296	4068295x	if(t == syntax_element_backref)
297	16417x	this->m_has_backrefs = true;
298		// append a new state, start by aligning our last one:
299	4068295x	m_pdata->m_data.align();
300		// set the offset to the next state in our last one:
301	4068295x	if(m_last_state)
302	3661404x	m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
303		// now actually extend our data:
304	4068295x	m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
305		// fill in boilerplate options in the new state:
306	4068295x	m_last_state->next.i = 0;
307	4068295x	m_last_state->type = t;
308	4068295x	return m_last_state;
309		}
310
311		template <class charT, class traits>
312	693104x	re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
313		{
314		// append a new state, start by aligning our last one:
315	693104x	m_pdata->m_data.align();
316		// set the offset to the next state in our last one:
317	693104x	if(m_last_state)
318	693104x	m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
319		// remember the last state position:
320	693104x	std::ptrdiff_t off = getoffset(m_last_state) + s;
321		// now actually insert our data:
322	693104x	re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
323		// fill in boilerplate options in the new state:
324	693104x	new_state->next.i = s;
325	693104x	new_state->type = t;
326	693104x	m_last_state = getaddress(off);
327	693104x	return new_state;
328		}
329
330		template <class charT, class traits>
331	1254190x	re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
332		{
333		re_literal* result;
334		// start by seeing if we have an existing re_literal we can extend:
335	1254190x	if((0 == m_last_state) \|\| (m_last_state->type != syntax_element_literal))
336		{
337		// no existing re_literal, create a new one:
338	830910x	result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
339	830910x	result->length = 1;
340	830910x	static_cast<charT>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
341		}
342		else
343		{
344		// we have an existing re_literal, extend it:
345	423280x	std::ptrdiff_t off = getoffset(m_last_state);
346	423280x	m_pdata->m_data.extend(sizeof(charT));
347	423280x	m_last_state = result = static_cast<re_literal*>(getaddress(off));
348	423280x	charT* characters = static_cast<charT>(static_cast<void>(result+1));
349	423280x	characters[result->length] = m_traits.translate(c, m_icase);
350	423280x	result->length += 1;
351		}
352	1254190x	return result;
353		}
354
355		template <class charT, class traits>
356	324508x	inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
357		const basic_char_set<charT, traits>& char_set)
358		{
359		typedef std::integral_constant<bool, (sizeof(charT) == 1) > truth_type;
360	324508x	return char_set.has_digraphs()
361	324508x	? append_set(char_set, static_cast<std::integral_constant<bool, false>*>(0))
362	324508x	: append_set(char_set, static_cast<truth_type*>(0));
363		}
364
365		template <class charT, class traits>
366	154351x	re_syntax_base* basic_regex_creator<charT, traits>::append_set(
367		const basic_char_set<charT, traits>& char_set, std::integral_constant<bool, false>*)
368		{
369		typedef typename traits::string_type string_type;
370		typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
371		typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
372		typedef typename traits::char_class_type m_type;
373
374	154351x	re_set_long<m_type>* result = static_cast<re_set_long<m_type>*>(append_state(syntax_element_long_set, sizeof(re_set_long<m_type>)));
375		//
376		// fill in the basics:
377		//
378	154351x	result->csingles = static_cast<unsigned int>(std::distance(char_set.singles_begin(), char_set.singles_end()));
379	154351x	result->cranges = static_cast<unsigned int>(std::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
380	154351x	result->cequivalents = static_cast<unsigned int>(std::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
381	154351x	result->cclasses = char_set.classes();
382	154351x	result->cnclasses = char_set.negated_classes();
383	154351x	if(flags() & regbase::icase)
384		{
385		// adjust classes as needed:
386	9912x	if(((result->cclasses & m_lower_mask) == m_lower_mask) \|\| ((result->cclasses & m_upper_mask) == m_upper_mask))
387	3180x	result->cclasses \|= m_alpha_mask;
388	9912x	if(((result->cnclasses & m_lower_mask) == m_lower_mask) \|\| ((result->cnclasses & m_upper_mask) == m_upper_mask))
389	✗	result->cnclasses \|= m_alpha_mask;
390		}
391
392	154351x	result->isnot = char_set.is_negated();
393	154351x	result->singleton = !char_set.has_digraphs();
394		//
395		// remember where the state is for later:
396		//
397	154351x	std::ptrdiff_t offset = getoffset(result);
398		//
399		// now extend with all the singles:
400		//
401	154351x	item_iterator first, last;
402	154351x	set_iterator sfirst, slast;
403	154351x	sfirst = char_set.singles_begin();
404	154351x	slast = char_set.singles_end();
405	314667x	while(sfirst != slast)
406		{
407	160316x	charT* p = static_cast<charT>(this->m_pdata->m_data.extend(sizeof(charT) (sfirst->first == static_cast<charT>(0) ? 1 : sfirst->second ? 3 : 2)));
408	160316x	p[0] = m_traits.translate(sfirst->first, m_icase);
409	160316x	if(sfirst->first == static_cast<charT>(0))
410		{
411	264x	p[0] = 0;
412		}
413	160052x	else if(sfirst->second)
414		{
415	13176x	p[1] = m_traits.translate(sfirst->second, m_icase);
416	13176x	p[2] = 0;
417		}
418		else
419	146876x	p[1] = 0;
420	160316x	++sfirst;
421		}
422		//
423		// now extend with all the ranges:
424		//
425	154351x	first = char_set.ranges_begin();
426	154351x	last = char_set.ranges_end();
427	194029x	while(first != last)
428		{
429		// first grab the endpoints of the range:
430	19839x	digraph<charT> c1 = *first;
431	19839x	c1.first = this->m_traits.translate(c1.first, this->m_icase);
432	19839x	c1.second = this->m_traits.translate(c1.second, this->m_icase);
433	19839x	++first;
434	19839x	digraph<charT> c2 = *first;
435	19839x	c2.first = this->m_traits.translate(c2.first, this->m_icase);
436	19839x	c2.second = this->m_traits.translate(c2.second, this->m_icase);
437	19839x	++first;
438	19839x	string_type s1, s2;
439		// different actions now depending upon whether collation is turned on:
440	19839x	if(flags() & regex_constants::collate)
441		{
442		// we need to transform our range into sort keys:
443	4080x	charT a1[3] = { c1.first, c1.second, charT(0), };
444	4080x	charT a2[3] = { c2.first, c2.second, charT(0), };
445	4080x	s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
446	4080x	s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
447	4080x	if(s1.empty())
448	288x	s1 = string_type(1, charT(0));
449	4080x	if(s2.empty())
450	96x	s2 = string_type(1, charT(0));
451		}
452		else
453		{
454	15759x	if(c1.second)
455		{
456	1260x	s1.insert(s1.end(), c1.first);
457	1260x	s1.insert(s1.end(), c1.second);
458		}
459		else
460	28998x	s1 = string_type(1, c1.first);
461	15759x	if(c2.second)
462		{
463	732x	s2.insert(s2.end(), c2.first);
464	732x	s2.insert(s2.end(), c2.second);
465		}
466		else
467	15027x	s2.insert(s2.end(), c2.first);
468		}
469	19839x	if(s1 > s2)
470		{
471		// Oops error:
472	432x	return 0;
473		}
474	19407x	charT* p = static_cast<charT>(this->m_pdata->m_data.extend(sizeof(charT) (s1.size() + s2.size() + 2) ) );
475	19407x	BOOST_REGEX_DETAIL_NS::copy(s1.begin(), s1.end(), p);
476	19407x	p[s1.size()] = charT(0);
477	19407x	p += s1.size() + 1;
478	19407x	BOOST_REGEX_DETAIL_NS::copy(s2.begin(), s2.end(), p);
479	19407x	p[s2.size()] = charT(0);
480		}
481		//
482		// now process the equivalence classes:
483		//
484	153919x	sfirst = char_set.equivalents_begin();
485	153919x	slast = char_set.equivalents_end();
486	155679x	while(sfirst != slast)
487		{
488	880x	string_type s;
489	880x	if(sfirst->second)
490		{
491	156x	charT cs[3] = { sfirst->first, sfirst->second, charT(0), };
492	156x	s = m_traits.transform_primary(cs, cs+2);
493		}
494		else
495	724x	s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
496	880x	if(s.empty())
497	✗	return 0; // invalid or unsupported equivalence class
498	880x	charT* p = static_cast<charT>(this->m_pdata->m_data.extend(sizeof(charT) (s.size()+1) ) );
499	880x	BOOST_REGEX_DETAIL_NS::copy(s.begin(), s.end(), p);
500	880x	p[s.size()] = charT(0);
501	880x	++sfirst;
502		}
503		//
504		// finally reset the address of our last state:
505		//
506	153919x	m_last_state = result = static_cast<re_set_long<m_type>*>(getaddress(offset));
507	153919x	return result;
508		}
509
510		template<class T>
511		inline bool char_less(T t1, T t2)
512		{
513		return t1 < t2;
514		}
515	114088x	inline bool char_less(char t1, char t2)
516		{
517	114088x	return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
518		}
519		inline bool char_less(signed char t1, signed char t2)
520		{
521		return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
522		}
523
524		template <class charT, class traits>
525	170157x	re_syntax_base* basic_regex_creator<charT, traits>::append_set(
526		const basic_char_set<charT, traits>& char_set, std::integral_constant<bool, true>*)
527		{
528		typedef typename traits::string_type string_type;
529		typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
530		typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
531
532	170157x	re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
533	170157x	bool negate = char_set.is_negated();
534	170157x	std::memset(result->_map, 0, sizeof(result->_map));
535		//
536		// handle singles first:
537		//
538	170157x	item_iterator first, last;
539	170157x	set_iterator sfirst, slast;
540	170157x	sfirst = char_set.singles_begin();
541	170157x	slast = char_set.singles_end();
542	664714x	while(sfirst != slast)
543		{
544	127101149x	for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
545		{
546	126606592x	if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
547	126606592x	== this->m_traits.translate(sfirst->first, this->m_icase))
548	495493x	result->_map[i] = true;
549		}
550	494557x	++sfirst;
551		}
552		//
553		// OK now handle ranges:
554		//
555	170157x	first = char_set.ranges_begin();
556	170157x	last = char_set.ranges_end();
557	285253x	while(first != last)
558		{
559		// first grab the endpoints of the range:
560	115192x	charT c1 = this->m_traits.translate(first->first, this->m_icase);
561	115192x	++first;
562	115192x	charT c2 = this->m_traits.translate(first->first, this->m_icase);
563	115192x	++first;
564		// different actions now depending upon whether collation is turned on:
565	115192x	if(flags() & regex_constants::collate)
566		{
567		// we need to transform our range into sort keys:
568	1104x	charT c3[2] = { c1, charT(0), };
569	1104x	string_type s1 = this->m_traits.transform(c3, c3+1);
570	1104x	c3[0] = c2;
571	1104x	string_type s2 = this->m_traits.transform(c3, c3+1);
572	1104x	if(s1 > s2)
573		{
574		// Oops error:
575	48x	return 0;
576		}
577	1056x	BOOST_REGEX_ASSERT(c3[1] == charT(0));
578	271392x	for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
579		{
580	270336x	c3[0] = static_cast<charT>(i);
581	270336x	string_type s3 = this->m_traits.transform(c3, c3 +1);
582	270336x	if((s1 <= s3) && (s3 <= s2))
583	14592x	result->_map[i] = true;
584		}
585	1152x	}
586		else
587		{
588	114088x	if(char_less(c2, c1))
589		{
590		// Oops error:
591	48x	return 0;
592		}
593		// everything in range matches:
594	114040x	std::memset(result->_map + static_cast<unsigned char>(c1), true, static_cast<unsigned char>(1u) + static_cast<unsigned char>(static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1)));
595		}
596		}
597		//
598		// and now the classes:
599		//
600		typedef typename traits::char_class_type m_type;
601	170061x	m_type m = char_set.classes();
602	170061x	if(flags() & regbase::icase)
603		{
604		// adjust m as needed:
605	3384x	if(((m & m_lower_mask) == m_lower_mask) \|\| ((m & m_upper_mask) == m_upper_mask))
606	720x	m \|= m_alpha_mask;
607		}
608	170061x	if(m != 0)
609		{
610	7438608x	for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
611		{
612	7409664x	if(this->m_traits.isctype(static_cast<charT>(i), m))
613	1013845x	result->_map[i] = true;
614		}
615		}
616		//
617		// and now the negated classes:
618		//
619	170061x	m = char_set.negated_classes();
620	170061x	if(flags() & regbase::icase)
621		{
622		// adjust m as needed:
623	3384x	if(((m & m_lower_mask) == m_lower_mask) \|\| ((m & m_upper_mask) == m_upper_mask))
624	✗	m \|= m_alpha_mask;
625		}
626	170061x	if(m != 0)
627		{
628	154200x	for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
629		{
630	153600x	if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
631	137880x	result->_map[i] = true;
632		}
633		}
634		//
635		// now process the equivalence classes:
636		//
637	170061x	sfirst = char_set.equivalents_begin();
638	170061x	slast = char_set.equivalents_end();
639	170541x	while(sfirst != slast)
640		{
641	240x	string_type s;
642	240x	BOOST_REGEX_ASSERT(static_cast<charT>(0) == sfirst->second);
643	240x	s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
644	240x	if(s.empty())
645	✗	return 0; // invalid or unsupported equivalence class
646	61680x	for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
647		{
648	61440x	charT c[2] = { (static_cast<charT>(i)), charT(0), };
649	61440x	string_type s2 = this->m_traits.transform_primary(c, c+1);
650	61440x	if(s == s2)
651	336x	result->_map[i] = true;
652		}
653	240x	++sfirst;
654		}
655	170061x	if(negate)
656		{
657	27233005x	for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
658		{
659	27127040x	result->_map[i] = !(result->_map[i]);
660		}
661		}
662	170061x	return result;
663		}
664
665		template <class charT, class traits>
666	360831x	void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
667		{
668	360831x	if(this->m_pdata->m_status)
669	822x	return;
670		// we've added all the states we need, now finish things off.
671		// start by adding a terminating state:
672	360009x	append_state(syntax_element_match);
673		// extend storage to store original expression:
674	360009x	std::ptrdiff_t len = p2 - p1;
675	360009x	m_pdata->m_expression_len = len;
676	360009x	charT* ps = static_cast<charT>(m_pdata->m_data.extend(sizeof(charT) (1 + (p2 - p1))));
677	360009x	m_pdata->m_expression = ps;
678	360009x	BOOST_REGEX_DETAIL_NS::copy(p1, p2, ps);
679	360009x	ps[p2 - p1] = 0;
680		// fill in our other data...
681		// successful parsing implies a zero status:
682	360009x	m_pdata->m_status = 0;
683		// get the first state of the machine:
684	360009x	m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
685		// fixup pointers in the machine:
686	360009x	fixup_pointers(m_pdata->m_first_state);
687	360009x	if(m_has_recursions)
688		{
689	34501x	m_pdata->m_has_recursions = true;
690	34501x	fixup_recursions(m_pdata->m_first_state);
691	33511x	if(this->m_pdata->m_status)
692	2154x	return;
693		}
694		else
695	325508x	m_pdata->m_has_recursions = false;
696		// create nested startmaps:
697	356865x	create_startmaps(m_pdata->m_first_state);
698		// create main startmap:
699	356425x	std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
700	356425x	m_pdata->m_can_be_null = 0;
701
702	356425x	m_bad_repeats = 0;
703	356425x	if(m_has_recursions)
704	31247x	m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
705	356425x	create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
706		// get the restart type:
707	356370x	m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
708		// optimise a leading repeat if there is one:
709	356370x	probe_leading_repeat(m_pdata->m_first_state);
710		}
711
712		template <class charT, class traits>
713	360009x	void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
714		{
715	4983012x	while(state)
716		{
717	4623003x	switch(state->type)
718		{
719	39626x	case syntax_element_recurse:
720	39626x	m_has_recursions = true;
721	39626x	if(state->next.i)
722	39626x	state->next.p = getaddress(state->next.i, state);
723		else
724	✗	state->next.p = 0;
725	39626x	break;
726	411233x	case syntax_element_rep:
727		case syntax_element_dot_rep:
728		case syntax_element_char_rep:
729		case syntax_element_short_set_rep:
730		case syntax_element_long_set_rep:
731		// set the state_id of this repeat:
732	411233x	static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
733		BOOST_REGEX_FALLTHROUGH;
734	667434x	case syntax_element_alt:
735	667434x	std::memset(static_cast<re_alt>(state)->_map, 0, sizeof(static_cast<re_alt>(state)->_map));
736	667434x	static_cast<re_alt*>(state)->can_be_null = 0;
737		BOOST_REGEX_FALLTHROUGH;
738	1388632x	case syntax_element_jump:
739	1388632x	static_cast<re_jump>(state)->alt.p = getaddress(static_cast<re_jump>(state)->alt.i, state);
740		BOOST_REGEX_FALLTHROUGH;
741	4583377x	default:
742	4583377x	if(state->next.i)
743	4223368x	state->next.p = getaddress(state->next.i, state);
744		else
745	360009x	state->next.p = 0;
746		}
747	4623003x	state = state->next.p;
748		}
749	360009x	}
750
751		template <class charT, class traits>
752	34501x	void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
753		{
754	34501x	re_syntax_base* base = state;
755	837127x	while(state)
756		{
757	803616x	switch(state->type)
758		{
759	4997x	case syntax_element_assert_backref:
760		{
761		// just check that the index is valid:
762	4997x	int idx = static_cast<const re_brace*>(state)->index;
763	4997x	if(idx < 0)
764		{
765	1217x	idx = -idx-1;
766	1217x	if(idx >= hash_value_mask)
767		{
768	905x	idx = m_pdata->get_id(idx);
769	905x	if(idx <= 0)
770		{
771		// check of sub-expression that doesn't exist:
772	168x	if(0 == this->m_pdata->m_status) // update the error code if not already set
773	168x	this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
774		//
775		// clear the expression, we should be empty:
776		//
777	168x	this->m_pdata->m_expression = 0;
778	168x	this->m_pdata->m_expression_len = 0;
779		//
780		// and throw if required:
781		//
782	168x	if(0 == (this->flags() & regex_constants::no_except))
783		{
784	60x	std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
785	60x	boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
786	60x	e.raise();
787	115x	}
788		}
789		}
790		}
791		}
792	4942x	break;
793	39461x	case syntax_element_recurse:
794		{
795	39461x	bool ok = false;
796	39461x	re_syntax_base* p = base;
797	39461x	std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
798	39461x	if(idx >= hash_value_mask)
799		{
800		//
801		// There may be more than one capture group with this hash, just do what Perl
802		// does and recurse to the leftmost:
803		//
804	9828x	idx = m_pdata->get_id(static_cast<int>(idx));
805		}
806	39461x	if(idx < 0)
807		{
808	2016x	ok = false;
809		}
810		else
811		{
812	243706x	while(p)
813		{
814	242746x	if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
815		{
816		//
817		// We've found the target of the recursion, set the jump target:
818		//
819	36485x	static_cast<re_jump*>(state)->alt.p = p;
820	36485x	ok = true;
821		//
822		// Now scan the target for nested repeats:
823		//
824	36485x	p = p->next.p;
825	36485x	int next_rep_id = 0;
826	396782x	while(p)
827		{
828	396782x	switch(p->type)
829		{
830	31192x	case syntax_element_rep:
831		case syntax_element_dot_rep:
832		case syntax_element_char_rep:
833		case syntax_element_short_set_rep:
834		case syntax_element_long_set_rep:
835	31192x	next_rep_id = static_cast<re_repeat*>(p)->state_id;
836	31192x	break;
837	42626x	case syntax_element_endmark:
838	42626x	if(static_cast<const re_brace*>(p)->index == idx)
839	21543x	next_rep_id = -1;
840	42626x	break;
841	322964x	default:
842	322964x	break;
843		}
844	396782x	if(next_rep_id)
845	36485x	break;
846	360297x	p = p->next.p;
847		}
848	36485x	if(next_rep_id > 0)
849		{
850	14942x	static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
851		}
852
853	36485x	break;
854		}
855	206261x	p = p->next.p;
856		}
857		}
858	39461x	if(!ok)
859		{
860		// recursion to sub-expression that doesn't exist:
861	2976x	if(0 == this->m_pdata->m_status) // update the error code if not already set
862	2976x	this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
863		//
864		// clear the expression, we should be empty:
865		//
866	2976x	this->m_pdata->m_expression = 0;
867	2976x	this->m_pdata->m_expression_len = 0;
868		//
869		// and throw if required:
870		//
871	2976x	if(0 == (this->flags() & regex_constants::no_except))
872		{
873	1020x	std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
874	1020x	boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
875	1020x	e.raise();
876	1955x	}
877		}
878		}
879	38526x	break;
880	759158x	default:
881	759158x	break;
882		}
883	802626x	state = state->next.p;
884		}
885	33511x	}
886
887		template <class charT, class traits>
888	356865x	void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
889		{
890		// non-recursive implementation:
891		// create the last map in the machine first, so that earlier maps
892		// can make use of the result...
893		//
894		// This was originally a recursive implementation, but that caused stack
895		// overflows with complex expressions on small stacks (think COM+).
896
897		// start by saving the case setting:
898	356865x	bool l_icase = m_icase;
899	356865x	std::vector<std::pair<bool, re_syntax_base*> > v;
900
901	4938394x	while(state)
902		{
903	4581859x	switch(state->type)
904		{
905	78170x	case syntax_element_toggle_case:
906		// we need to track case changes here:
907	78170x	m_icase = static_cast<re_case*>(state)->icase;
908	78170x	state = state->next.p;
909	78170x	continue;
910	666381x	case syntax_element_alt:
911		case syntax_element_rep:
912		case syntax_element_dot_rep:
913		case syntax_element_char_rep:
914		case syntax_element_short_set_rep:
915		case syntax_element_long_set_rep:
916		// just push the state onto our stack for now:
917	666381x	v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
918	666381x	state = state->next.p;
919	666381x	break;
920	8354x	case syntax_element_backstep:
921		// we need to calculate how big the backstep is:
922	8354x	static_cast<re_brace*>(state)->index
923	8354x	= this->calculate_backstep(state->next.p);
924	8354x	if(static_cast<re_brace*>(state)->index < 0)
925		{
926		// Oops error:
927	1152x	if(0 == this->m_pdata->m_status) // update the error code if not already set
928	1152x	this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
929		//
930		// clear the expression, we should be empty:
931		//
932	1152x	this->m_pdata->m_expression = 0;
933	1152x	this->m_pdata->m_expression_len = 0;
934		//
935		// and throw if required:
936		//
937	1152x	if(0 == (this->flags() & regex_constants::no_except))
938		{
939	360x	std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
940	360x	boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
941	360x	e.raise();
942	690x	}
943		}
944		BOOST_REGEX_FALLTHROUGH;
945		default:
946	3836978x	state = state->next.p;
947	78170x	}
948		}
949
950		// now work through our list, building all the maps as we go:
951	1013456x	while(!v.empty())
952		{
953		// Initialize m_recursion_checks if we need it:
954	657031x	if(m_has_recursions)
955	107493x	m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
956
957	657031x	const std::pair<bool, re_syntax_base*>& p = v.back();
958	657031x	m_icase = p.first;
959	657031x	state = p.second;
960	657031x	v.pop_back();
961
962		// Build maps:
963	657031x	m_bad_repeats = 0;
964	657031x	create_startmap(state->next.p, static_cast<re_alt>(state)->_map, &static_cast<re_alt>(state)->can_be_null, mask_take);
965	656976x	m_bad_repeats = 0;
966
967	656976x	if(m_has_recursions)
968	107438x	m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
969	656976x	create_startmap(static_cast<re_alt>(state)->alt.p, static_cast<re_alt>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_skip);
970		// adjust the type of the state to allow for faster matching:
971	656921x	state->type = this->get_repeat_type(state);
972		}
973		// restore case sensitivity:
974	356425x	m_icase = l_icase;
975	356865x	}
976
977		template <class charT, class traits>
978	8354x	int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
979		{
980		typedef typename traits::char_class_type m_type;
981
982	8354x	int result = 0;
983	8354x	int last_alternative_result = -1;
984
985	8354x	std::vector<std::tuple<int, re_syntax_base*>> stack;
986
987	34399x	while(state)
988		{
989	34399x	switch(state->type)
990		{
991	1802x	case syntax_element_startmark:
992	1802x	if((static_cast<re_brace*>(state)->index == -1)
993	1622x	\|\| (static_cast<re_brace*>(state)->index == -2))
994		{
995	360x	state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
996	360x	continue;
997		}
998	1442x	else if(static_cast<re_brace*>(state)->index == -3)
999		{
1000	180x	state = state->next.p->next.p;
1001	180x	continue;
1002		}
1003	1262x	break;
1004	13412x	case syntax_element_endmark:
1005	13412x	if ((static_cast<re_brace*>(state)->index == -1)
1006	5086x	\|\| (static_cast<re_brace*>(state)->index == -2))
1007		{
1008		// We've finished the calculation, check against any previous alternatives:
1009	9970x	if (last_alternative_result >= 0)
1010		{
1011	2384x	if (last_alternative_result != result)
1012	384x	return -1;
1013		}
1014		else
1015	7586x	last_alternative_result = result;
1016
1017	9586x	if (stack.size())
1018		{
1019		// Skip to next alternative and calculate that as well:
1020	2384x	std::tie(result, state) = stack.back();
1021	2384x	stack.pop_back();
1022	2384x	continue;
1023		}
1024		else
1025	7202x	return result;
1026		}
1027	3442x	break;
1028	7709x	case syntax_element_literal:
1029	7709x	result += static_cast<re_literal*>(state)->length;
1030	7709x	break;
1031	240x	case syntax_element_wild:
1032		case syntax_element_set:
1033	240x	result += 1;
1034	240x	break;
1035	1836x	case syntax_element_dot_rep:
1036		case syntax_element_char_rep:
1037		case syntax_element_short_set_rep:
1038		case syntax_element_backref:
1039		case syntax_element_rep:
1040		case syntax_element_combining:
1041		case syntax_element_long_set_rep:
1042		case syntax_element_backstep:
1043		{
1044	1836x	re_repeat* rep = static_cast<re_repeat *>(state);
1045		// adjust the type of the state to allow for faster matching:
1046	1836x	state->type = this->get_repeat_type(state);
1047	1836x	if((state->type == syntax_element_dot_rep)
1048	1296x	\|\| (state->type == syntax_element_char_rep)
1049	744x	\|\| (state->type == syntax_element_short_set_rep))
1050		{
1051	1212x	if(rep->max != rep->min)
1052	192x	return -1;
1053	1020x	if (static_cast<std::size_t>((std::numeric_limits<int>::max)() - result) < rep->min)
1054	✗	return -1; // protection against overflow, we can't calculate a backstep in this case and the expression is probably ill-formed.
1055	1020x	result += static_cast<int>(rep->min);
1056	1020x	state = rep->alt.p;
1057	1020x	continue;
1058		}
1059	624x	else if(state->type == syntax_element_long_set_rep)
1060		{
1061	240x	BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_long_set);
1062	240x	if(static_cast<re_set_long<m_type>*>(rep->next.p)->singleton == 0)
1063	✗	return -1;
1064	240x	if(rep->max != rep->min)
1065	✗	return -1;
1066	240x	result += static_cast<int>(rep->min);
1067	240x	state = rep->alt.p;
1068	240x	continue;
1069		}
1070		}
1071	384x	return -1;
1072	672x	case syntax_element_long_set:
1073	672x	if(static_cast<re_set_long<m_type>*>(state)->singleton == 0)
1074	192x	return -1;
1075	480x	result += 1;
1076	480x	break;
1077	2384x	case syntax_element_jump:
1078	2384x	state = static_cast<re_jump*>(state)->alt.p;
1079	2384x	continue;
1080	2384x	case syntax_element_alt:
1081		{
1082		// Push the alternative if we haven't pushed too many already:
1083	2384x	if(stack.size() > BOOST_REGEX_MAX_BLOCKS)
1084	✗	return -1;
1085	2384x	stack.push_back(std::make_tuple(result, static_cast<re_alt*>(state)->alt.p));
1086		// and take the first one:
1087	2384x	state = state->next.p;
1088	2384x	continue;
1089		}
1090	3960x	default:
1091	3960x	break;
1092	4768x	}
1093	17093x	state = state->next.p;
1094		}
1095	✗	return -1;
1096	8354x	}
1097
1098		struct recursion_saver
1099		{
1100		std::vector<unsigned char> saved_state;
1101		std::vector<unsigned char>* state;
1102	2020488x	recursion_saver(std::vector<unsigned char>* p) : saved_state(*p), state(p) {}
1103	2020488x	~recursion_saver()
1104		{
1105	2020488x	state->swap(saved_state);
1106	2020488x	}
1107		};
1108
1109		template <class charT, class traits>
1110	2020488x	void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask, unsigned recursion_count)
1111		{
1112	2020488x	recursion_saver saved_recursions(&m_recursion_checks);
1113	2020488x	int not_last_jump = 1;
1114	2020488x	re_syntax_base* recursion_start = 0;
1115	2020488x	int recursion_sub = 0;
1116	2020488x	re_syntax_base* recursion_restart = 0;
1117
1118		// track case sensitivity:
1119	2020488x	bool l_icase = m_icase;
1120
1121	2020488x	if (recursion_count > BOOST_REGEX_MAX_RECURSION_DEPTH)
1122		{
1123		// Oops error:
1124	521x	if (0 == this->m_pdata->m_status) // update the error code if not already set
1125	384x	this->m_pdata->m_status = boost::regex_constants::error_complexity;
1126		//
1127		// clear the expression, we should be empty:
1128		//
1129	521x	this->m_pdata->m_expression = 0;
1130	521x	this->m_pdata->m_expression_len = 0;
1131		//
1132		// and throw if required:
1133		//
1134	521x	if (0 == (this->flags() & regex_constants::no_except))
1135		{
1136	125x	std::string message = "Expression complexity exceeded.";
1137	125x	boost::regex_error e(message, boost::regex_constants::error_complexity, 0);
1138	125x	e.raise();
1139	235x	}
1140	411x	return;
1141		}
1142
1143	3514946x	while(state)
1144		{
1145	3514946x	switch(state->type)
1146		{
1147	17485x	case syntax_element_toggle_case:
1148	17485x	l_icase = static_cast<re_case*>(state)->icase;
1149	17485x	state = state->next.p;
1150	17485x	break;
1151	726782x	case syntax_element_literal:
1152		{
1153		// don't set anything in *pnull, set each element in l_map
1154		// that could match the first character in the literal:
1155	726782x	if(l_map)
1156		{
1157	726782x	l_map[0] \|= mask_init;
1158	726782x	charT first_char = static_cast<charT>(static_cast<void>(static_cast<re_literal>(state) + 1));
1159	186782974x	for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1160		{
1161	186056192x	if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
1162	746544x	l_map[i] \|= mask;
1163		}
1164		}
1165	726782x	return;
1166		}
1167	31324x	case syntax_element_end_line:
1168		{
1169		// next character must be a line separator (if there is one):
1170	31324x	if(l_map)
1171		{
1172	12124x	l_map[0] \|= mask_init;
1173	12124x	l_map[static_cast<unsigned>('\n')] \|= mask;
1174	12124x	l_map[static_cast<unsigned>('\r')] \|= mask;
1175	12124x	l_map[static_cast<unsigned>('\f')] \|= mask;
1176	12124x	l_map[0x85] \|= mask;
1177		}
1178		// now figure out if we can match a NULL string at this point:
1179	31324x	if(pnull)
1180	31324x	create_startmap(state->next.p, 0, pnull, mask, ++recursion_count);
1181	25769x	return;
1182		}
1183	24121x	case syntax_element_recurse:
1184		{
1185	24121x	BOOST_REGEX_ASSERT(static_cast<const re_jump*>(state)->alt.p->type == syntax_element_startmark);
1186	24121x	recursion_sub = static_cast<re_brace>(static_cast<const re_jump>(state)->alt.p)->index;
1187	24121x	if(m_recursion_checks[recursion_sub] & 1u)
1188		{
1189		// Infinite recursion!!
1190	192x	if(0 == this->m_pdata->m_status) // update the error code if not already set
1191	192x	this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
1192		//
1193		// clear the expression, we should be empty:
1194		//
1195	192x	this->m_pdata->m_expression = 0;
1196	192x	this->m_pdata->m_expression_len = 0;
1197		//
1198		// and throw if required:
1199		//
1200	192x	if(0 == (this->flags() & regex_constants::no_except))
1201		{
1202	60x	std::string message = "Encountered an infinite recursion.";
1203	60x	boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
1204	60x	e.raise();
1205	115x	}
1206		}
1207	23929x	else if(recursion_start == 0)
1208		{
1209	23929x	recursion_start = state;
1210	23929x	recursion_restart = state->next.p;
1211	23929x	state = static_cast<re_jump*>(state)->alt.p;
1212	23929x	m_recursion_checks[recursion_sub] \|= 1u;
1213	23929x	break;
1214		}
1215	137x	m_recursion_checks[recursion_sub] \|= 1u;
1216		// can't handle nested recursion here...
1217		BOOST_REGEX_FALLTHROUGH;
1218		}
1219	2969x	case syntax_element_backref:
1220		// can be null, and any character can match:
1221	2969x	if(pnull)
1222	2969x	*pnull \|= mask;
1223		BOOST_REGEX_FALLTHROUGH;
1224		case syntax_element_wild:
1225		{
1226		// can't be null, any character can match:
1227	48825x	set_all_masks(l_map, mask);
1228	48825x	return;
1229		}
1230	192697x	case syntax_element_accept:
1231		case syntax_element_match:
1232		{
1233		// must be null, any character can match:
1234	192697x	set_all_masks(l_map, mask);
1235	192697x	if(pnull)
1236	192697x	*pnull \|= mask;
1237	192697x	return;
1238		}
1239	5400x	case syntax_element_word_start:
1240		{
1241		// recurse, then AND with all the word characters:
1242	5400x	create_startmap(state->next.p, l_map, pnull, mask, ++recursion_count);
1243	5400x	if(l_map)
1244		{
1245	5400x	l_map[0] \|= mask_init;
1246	1387800x	for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1247		{
1248	1382400x	if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
1249	917400x	l_map[i] &= static_cast<unsigned char>(~mask);
1250		}
1251		}
1252	5400x	return;
1253		}
1254	2292x	case syntax_element_word_end:
1255		{
1256		// recurse, then AND with all the word characters:
1257	2292x	create_startmap(state->next.p, l_map, pnull, mask, ++recursion_count);
1258	2292x	if(l_map)
1259		{
1260	2292x	l_map[0] \|= mask_init;
1261	589044x	for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1262		{
1263	586752x	if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
1264	198996x	l_map[i] &= static_cast<unsigned char>(~mask);
1265		}
1266		}
1267	2292x	return;
1268		}
1269	1059x	case syntax_element_buffer_end:
1270		{
1271		// we must be null :
1272	1059x	if(pnull)
1273	1059x	*pnull \|= mask;
1274	1059x	return;
1275		}
1276	116597x	case syntax_element_long_set:
1277	116597x	if(l_map)
1278		{
1279		typedef typename traits::char_class_type m_type;
1280	116597x	if(static_cast<re_set_long<m_type>*>(state)->singleton)
1281		{
1282	103805x	l_map[0] \|= mask_init;
1283	26677885x	for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1284		{
1285	26574080x	charT c = static_cast<charT>(i);
1286	26574080x	if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<m_type>>(state), m_pdata, l_icase))
1287	10062246x	l_map[i] \|= mask;
1288		}
1289		}
1290		else
1291	12792x	set_all_masks(l_map, mask);
1292		}
1293	116597x	return;
1294	107567x	case syntax_element_set:
1295	107567x	if(l_map)
1296		{
1297	107567x	l_map[0] \|= mask_init;
1298	27644719x	for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1299		{
1300	27537152x	if(static_cast<re_set*>(state)->_map[
1301	27537152x	static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1302	9898680x	l_map[i] \|= mask;
1303		}
1304		}
1305	107567x	return;
1306	266514x	case syntax_element_jump:
1307		// take the jump:
1308	266514x	state = static_cast<re_alt*>(state)->alt.p;
1309	266514x	not_last_jump = -1;
1310	266514x	break;
1311	723044x	case syntax_element_alt:
1312		case syntax_element_rep:
1313		case syntax_element_dot_rep:
1314		case syntax_element_char_rep:
1315		case syntax_element_short_set_rep:
1316		case syntax_element_long_set_rep:
1317		{
1318	723044x	re_alt* rep = static_cast<re_alt*>(state);
1319	723044x	if(rep->_map[0] & mask_init)
1320		{
1321	468152x	if(l_map)
1322		{
1323		// copy previous results:
1324	468148x	l_map[0] \|= mask_init;
1325	120314036x	for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1326		{
1327	119845888x	if(rep->_map[i] & mask_any)
1328	79330963x	l_map[i] \|= mask;
1329		}
1330		}
1331	468152x	if(pnull)
1332		{
1333	468152x	if(rep->can_be_null & mask_any)
1334	282011x	*pnull \|= mask;
1335		}
1336		}
1337		else
1338		{
1339		// we haven't created a startmap for this alternative yet
1340		// so take the union of the two options:
1341	254892x	if(is_bad_repeat(state))
1342		{
1343	100291x	set_all_masks(l_map, mask);
1344	100291x	if(pnull)
1345	100291x	*pnull \|= mask;
1346	100291x	return;
1347		}
1348	154601x	set_bad_repeat(state);
1349	154601x	create_startmap(state->next.p, l_map, pnull, mask, ++recursion_count);
1350	154491x	if((state->type == syntax_element_alt)
1351	135050x	\|\| (static_cast<re_repeat*>(state)->min == 0)
1352	127050x	\|\| (not_last_jump == 0))
1353	152946x	create_startmap(rep->alt.p, l_map, pnull, mask, ++recursion_count);
1354		}
1355		}
1356	619893x	return;
1357	180x	case syntax_element_soft_buffer_end:
1358		// match newline or null:
1359	180x	if(l_map)
1360		{
1361	180x	l_map[0] \|= mask_init;
1362	180x	l_map[static_cast<unsigned>('\n')] \|= mask;
1363	180x	l_map[static_cast<unsigned>('\r')] \|= mask;
1364		}
1365	180x	if(pnull)
1366	180x	*pnull \|= mask;
1367	180x	return;
1368	338427x	case syntax_element_endmark:
1369		// need to handle independent subs as a special case:
1370	338427x	if(static_cast<re_brace*>(state)->index < 0)
1371		{
1372		// can be null, any character can match:
1373	64145x	set_all_masks(l_map, mask);
1374	64145x	if(pnull)
1375	64145x	*pnull \|= mask;
1376	64145x	return;
1377		}
1378	274282x	else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
1379		{
1380		// recursion termination:
1381	✗	recursion_start = 0;
1382	✗	state = recursion_restart;
1383	✗	break;
1384		}
1385
1386		//
1387		// Normally we just go to the next state... but if this sub-expression is
1388		// the target of a recursion, then we might be ending a recursion, in which
1389		// case we should check whatever follows that recursion, as well as whatever
1390		// follows this state:
1391		//
1392	274282x	if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
1393		{
1394	43755x	bool ok = false;
1395	43755x	re_syntax_base* p = m_pdata->m_first_state;
1396	11466864x	while(p)
1397		{
1398	11426602x	if(p->type == syntax_element_recurse)
1399		{
1400	44943x	re_brace* p2 = static_cast<re_brace>(static_cast<re_jump>(p)->alt.p);
1401	44943x	if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
1402		{
1403	3493x	ok = true;
1404	3493x	break;
1405		}
1406		}
1407	11423109x	p = p->next.p;
1408		}
1409	43755x	if(ok && ((m_recursion_checks[static_cast<re_brace*>(state)->index] & 2u) == 0))
1410		{
1411	3493x	m_recursion_checks[static_cast<re_brace*>(state)->index] \|= 2u;
1412	3493x	create_startmap(p->next.p, l_map, pnull, mask, ++recursion_count);
1413		}
1414		}
1415	274282x	state = state->next.p;
1416	274282x	break;
1417
1418	2161x	case syntax_element_commit:
1419	2161x	set_all_masks(l_map, mask);
1420		// Continue scanning so we can figure out whether we can be null:
1421	2161x	state = state->next.p;
1422	2161x	break;
1423	859448x	case syntax_element_startmark:
1424		// need to handle independent subs as a special case:
1425	859448x	if(static_cast<re_brace*>(state)->index == -3)
1426		{
1427	25968x	state = state->next.p->next.p;
1428	25968x	break;
1429		}
1430		BOOST_REGEX_FALLTHROUGH;
1431		default:
1432	884640x	state = state->next.p;
1433		}
1434	1494979x	++not_last_jump;
1435		}
1436	2020488x	}
1437
1438		template <class charT, class traits>
1439	356370x	unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1440		{
1441		//
1442		// find out how the machine starts, so we can optimise the search:
1443		//
1444	1073446x	while(state)
1445		{
1446	754187x	switch(state->type)
1447		{
1448	397817x	case syntax_element_startmark:
1449		case syntax_element_endmark:
1450	397817x	state = state->next.p;
1451	397817x	continue;
1452	28924x	case syntax_element_start_line:
1453	28924x	return regbase::restart_line;
1454	5196x	case syntax_element_word_start:
1455	5196x	return regbase::restart_word;
1456	2271x	case syntax_element_buffer_start:
1457	2271x	return regbase::restart_buf;
1458	720x	case syntax_element_restart_continue:
1459	720x	return regbase::restart_continue;
1460	319259x	default:
1461	319259x	state = 0;
1462	319259x	continue;
1463		}
1464		}
1465	319259x	return regbase::restart_any;
1466		}
1467
1468		template <class charT, class traits>
1469	420911x	void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1470		{
1471		//
1472		// set mask in all of bits elements,
1473		// if bits[0] has mask_init not set then we can
1474		// optimise this to a call to memset:
1475		//
1476	420911x	if(bits)
1477		{
1478	408983x	if(bits[0] == 0)
1479	105610x	(std::memset)(bits, mask, 1u << CHAR_BIT);
1480		else
1481		{
1482	77966861x	for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1483	77663488x	bits[i] \|= mask;
1484		}
1485	408983x	bits[0] \|= mask_init;
1486		}
1487	420911x	}
1488
1489		template <class charT, class traits>
1490	254892x	bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1491		{
1492	254892x	switch(pt->type)
1493		{
1494	235341x	case syntax_element_rep:
1495		case syntax_element_dot_rep:
1496		case syntax_element_char_rep:
1497		case syntax_element_short_set_rep:
1498		case syntax_element_long_set_rep:
1499		{
1500	235341x	unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1501	235341x	if(state_id >= sizeof(m_bad_repeats) * CHAR_BIT)
1502	8100x	return true; // run out of bits, assume we can't traverse this one.
1503		static const std::uintmax_t one = 1uL;
1504	227241x	return m_bad_repeats & (one << state_id);
1505		}
1506	19551x	default:
1507	19551x	return false;
1508		}
1509		}
1510
1511		template <class charT, class traits>
1512	154601x	void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1513		{
1514	154601x	switch(pt->type)
1515		{
1516	135050x	case syntax_element_rep:
1517		case syntax_element_dot_rep:
1518		case syntax_element_char_rep:
1519		case syntax_element_short_set_rep:
1520		case syntax_element_long_set_rep:
1521		{
1522	135050x	unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1523		static const std::uintmax_t one = 1uL;
1524	135050x	if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
1525	135050x	m_bad_repeats \|= (one << state_id);
1526		}
1527	135050x	break;
1528	19551x	default:
1529	19551x	break;
1530		}
1531	154601x	}
1532
1533		template <class charT, class traits>
1534	658757x	syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1535		{
1536		typedef typename traits::char_class_type m_type;
1537	658757x	if(state->type == syntax_element_rep)
1538		{
1539		// check to see if we are repeating a single state:
1540	411013x	if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1541		{
1542	256193x	switch(state->next.p->type)
1543		{
1544	33179x	case BOOST_REGEX_DETAIL_NS::syntax_element_wild:
1545	33179x	return BOOST_REGEX_DETAIL_NS::syntax_element_dot_rep;
1546	102127x	case BOOST_REGEX_DETAIL_NS::syntax_element_literal:
1547	102127x	return BOOST_REGEX_DETAIL_NS::syntax_element_char_rep;
1548	41861x	case BOOST_REGEX_DETAIL_NS::syntax_element_set:
1549	41861x	return BOOST_REGEX_DETAIL_NS::syntax_element_short_set_rep;
1550	78844x	case BOOST_REGEX_DETAIL_NS::syntax_element_long_set:
1551	78844x	if(static_cast<BOOST_REGEX_DETAIL_NS::re_set_long<m_type>*>(state->next.p)->singleton)
1552	72772x	return BOOST_REGEX_DETAIL_NS::syntax_element_long_set_rep;
1553	6072x	break;
1554	182x	default:
1555	182x	break;
1556		}
1557		}
1558		}
1559	408818x	return state->type;
1560		}
1561
1562		template <class charT, class traits>
1563	356370x	void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1564		{
1565		// enumerate our states, and see if we have a leading repeat
1566		// for which failed search restarts can be optimized;
1567		do
1568		{
1569	829945x	switch(state->type)
1570		{
1571	408300x	case syntax_element_startmark:
1572	408300x	if(static_cast<re_brace*>(state)->index >= 0)
1573		{
1574	388409x	state = state->next.p;
1575	388409x	continue;
1576		}
1577		#ifdef BOOST_REGEX_MSVC
1578		# pragma warning(push)
1579		#pragma warning(disable:6011)
1580		#endif
1581	19891x	if((static_cast<re_brace*>(state)->index == -1)
1582	12906x	\|\| (static_cast<re_brace*>(state)->index == -2))
1583		{
1584		// skip past the zero width assertion:
1585	8562x	state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
1586	8562x	continue;
1587		}
1588		#ifdef BOOST_REGEX_MSVC
1589		# pragma warning(pop)
1590		#endif
1591	11329x	if(static_cast<re_brace*>(state)->index == -3)
1592		{
1593		// Have to skip the leading jump state:
1594	6505x	state = state->next.p->next.p;
1595	6505x	continue;
1596		}
1597	4824x	return;
1598	70099x	case syntax_element_endmark:
1599		case syntax_element_start_line:
1600		case syntax_element_end_line:
1601		case syntax_element_word_boundary:
1602		case syntax_element_within_word:
1603		case syntax_element_word_start:
1604		case syntax_element_word_end:
1605		case syntax_element_buffer_start:
1606		case syntax_element_buffer_end:
1607		case syntax_element_restart_continue:
1608	70099x	state = state->next.p;
1609	70099x	break;
1610	71125x	case syntax_element_dot_rep:
1611		case syntax_element_char_rep:
1612		case syntax_element_short_set_rep:
1613		case syntax_element_long_set_rep:
1614	71125x	if(this->m_has_backrefs == 0)
1615	70405x	static_cast<re_repeat*>(state)->leading = true;
1616		BOOST_REGEX_FALLTHROUGH;
1617		default:
1618	351546x	return;
1619		}
1620	473575x	}while(state);
1621		}
1622
1623		} // namespace BOOST_REGEX_DETAIL_NS
1624
1625		} // namespace boost
1626
1627		#ifdef BOOST_REGEX_MSVC
1628		# pragma warning(pop)
1629		#endif
1630
1631		#endif
1632