include/boost/regex/v5/perl_matcher_non_recursive.hpp

95.9% Lines (873/910) 48.7% List of functions (930/1911)

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

perl_matcher_non_recursive.hpp

f(x) Functions (1911)

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		/*
13		* LOCATION: see http://www.boost.org for most recent version.
14		* FILE perl_matcher_common.cpp
15		* VERSION see <boost/version.hpp>
16		* DESCRIPTION: Definitions of perl_matcher member functions that are
17		* specific to the non-recursive implementation.
18		*/
19
20		#ifndef BOOST_REGEX_V5_PERL_MATCHER_NON_RECURSIVE_HPP
21		#define BOOST_REGEX_V5_PERL_MATCHER_NON_RECURSIVE_HPP
22
23		#include <boost/regex/config.hpp>
24
25		#ifndef BOOST_REGEX_STANDALONE
26
27		#include <boost/config.hpp>
28		#if defined(BOOST_HAS_PRAGMA_ONCE)
29		#pragma once
30		#include <boost/regex/v5/perl_matcher.hpp>
31		#endif
32
33		#endif
34
35		#include <boost/regex/v5/mem_block_cache.hpp>
36
37		#ifdef BOOST_REGEX_MSVC
38		# pragma warning(push)
39		# pragma warning(disable: 4706 4459)
40		#if BOOST_REGEX_MSVC < 1910
41		#pragma warning(disable:4800)
42		#endif
43		#endif
44
45		namespace boost{
46		namespace BOOST_REGEX_DETAIL_NS{
47
48		template <class T>
49	20246528x	inline void inplace_destroy(T* p)
50		{
51		(void)p; // warning suppression
52	20246528x	p->~T();
53	20246528x	}
54
55		struct saved_state
56		{
57		union{
58		unsigned int state_id;
59		// this padding ensures correct alignment on 64-bit platforms:
60		std::size_t padding1;
61		std::ptrdiff_t padding2;
62		void* padding3;
63		};
64	21976895x	saved_state(unsigned i) : state_id(i) {}
65		};
66
67		template <class BidiIterator>
68		struct saved_matched_paren : public saved_state
69		{
70		int index;
71		sub_match<BidiIterator> sub;
72	4570538x	saved_matched_paren(int i, const sub_match<BidiIterator>& s) : saved_state(1), index(i), sub(s){}
73		};
74
75		template <class BidiIterator>
76		struct saved_position : public saved_state
77		{
78		const re_syntax_base* pstate;
79		BidiIterator position;
80	1569610x	saved_position(const re_syntax_base* ps, BidiIterator pos, int i) : saved_state(i), pstate(ps), position(pos){}
81		};
82
83		template <class BidiIterator>
84		struct saved_assertion : public saved_position<BidiIterator>
85		{
86		bool positive;
87	267659x	saved_assertion(bool p, const re_syntax_base* ps, BidiIterator pos)
88	267659x	: saved_position<BidiIterator>(ps, pos, saved_type_assertion), positive(p){}
89		};
90
91		template <class BidiIterator>
92	✗	struct saved_repeater : public saved_state
93		{
94		repeater_count<BidiIterator> count;
95	5751305x	saved_repeater(int i, repeater_count<BidiIterator>** s, BidiIterator start, int current_recursion_id)
96	5751305x	: saved_state(saved_state_repeater_count), count(i, s, start, current_recursion_id){}
97		};
98
99		struct saved_extra_block : public saved_state
100		{
101		saved_state base, end;
102	37964x	saved_extra_block(saved_state* b, saved_state* e)
103	37964x	: saved_state(saved_state_extra_block), base(b), end(e) {}
104		};
105
106		struct save_state_init
107		{
108		saved_state** stack;
109	1730367x	save_state_init(saved_state base, saved_state end)
110	1730367x	: stack(base)
111		{
112	1730367x	base = static_cast<saved_state>(get_mem_block());
113	1730367x	end = reinterpret_cast<saved_state>(reinterpret_cast<char>(base)+BOOST_REGEX_BLOCKSIZE);
114	1730367x	--(*end);
115	1730367x	(void) new (*end)saved_state(0);
116	1730367x	BOOST_REGEX_ASSERT(end > base);
117	1730367x	}
118	1730367x	~save_state_init()
119		{
120	1730367x	put_mem_block(*stack);
121	1730367x	*stack = 0;
122	1730367x	}
123		};
124
125		template <class BidiIterator>
126		struct saved_single_repeat : public saved_state
127		{
128		std::size_t count;
129		const re_repeat* rep;
130		BidiIterator last_position;
131	4107363x	saved_single_repeat(std::size_t c, const re_repeat* r, BidiIterator lp, int arg_id)
132	4107363x	: saved_state(arg_id), count(c), rep(r), last_position(lp){}
133		};
134
135		template <class Results>
136	✗	struct saved_recursion : public saved_state
137		{
138	525557x	saved_recursion(int idx, const re_syntax_base* p, Results* pr, Results* pr2)
139	525557x	: saved_state(14), recursion_id(idx), preturn_address(p), internal_results(pr), prior_results(pr2) {}
140		int recursion_id;
141		const re_syntax_base* preturn_address;
142		Results internal_results, prior_results;
143		};
144
145		struct saved_change_case : public saved_state
146		{
147		bool icase;
148	108360x	saved_change_case(bool c) : saved_state(18), icase(c) {}
149		};
150
151		struct incrementer
152		{
153	3020252x	incrementer(unsigned* pu) : m_pu(pu) { ++*m_pu; }
154	3020252x	~incrementer() { --*m_pu; }
155	3020252x	bool operator > (unsigned i) { return *m_pu > i; }
156		private:
157		unsigned* m_pu;
158		};
159
160		template <class BidiIterator, class Allocator, class traits>
161	3020252x	bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
162		{
163		static matcher_proc_type const s_match_vtable[34] =
164		{
165		(&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
166		&perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
167		&perl_matcher<BidiIterator, Allocator, traits>::match_literal,
168		&perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
169		&perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
170		&perl_matcher<BidiIterator, Allocator, traits>::match_wild,
171		&perl_matcher<BidiIterator, Allocator, traits>::match_match,
172		&perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
173		&perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
174		&perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
175		&perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
176		&perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
177		&perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
178		&perl_matcher<BidiIterator, Allocator, traits>::match_backref,
179		&perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
180		&perl_matcher<BidiIterator, Allocator, traits>::match_set,
181		&perl_matcher<BidiIterator, Allocator, traits>::match_jump,
182		&perl_matcher<BidiIterator, Allocator, traits>::match_alt,
183		&perl_matcher<BidiIterator, Allocator, traits>::match_rep,
184		&perl_matcher<BidiIterator, Allocator, traits>::match_combining,
185		&perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
186		&perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
187		// Although this next line should be evaluated at compile time, in practice
188		// some compilers (VC++) emit run-time initialisation which breaks thread
189		// safety, so use a dispatch function instead:
190		//(::boost::is_random_access_iterator<BidiIterator>::value ? &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast : &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow),
191		&perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
192		&perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
193		&perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
194		&perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
195		&perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
196		&perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
197		&perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
198		&perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
199		&perl_matcher<BidiIterator, Allocator, traits>::match_fail,
200		&perl_matcher<BidiIterator, Allocator, traits>::match_accept,
201		&perl_matcher<BidiIterator, Allocator, traits>::match_commit,
202		&perl_matcher<BidiIterator, Allocator, traits>::match_then,
203		};
204	3020252x	incrementer inc(&m_recursions);
205	3020252x	if(inc > 80)
206	✗	raise_error(traits_inst, regex_constants::error_complexity);
207	3020252x	push_recursion_stopper();
208		do{
209	75670394x	while(pstate)
210		{
211	74616260x	matcher_proc_type proc = s_match_vtable[pstate->type];
212	74616260x	++state_count;
213	74616260x	if(!(this->*proc)())
214		{
215	37848664x	if(state_count > max_state_count)
216	5x	raise_error(traits_inst, regex_constants::error_complexity);
217	37848659x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
218	22599x	m_has_partial_match = true;
219	37848659x	bool successful_unwind = unwind(false);
220	37848659x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
221	9480x	m_has_partial_match = true;
222	37848659x	if(!successful_unwind)
223	2078815x	return m_recursive_result;
224		}
225		}
226	1054134x	}while(unwind(true));
227	941424x	return m_recursive_result;
228	3020252x	}
229
230		template <class BidiIterator, class Allocator, class traits>
231	37972x	void perl_matcher<BidiIterator, Allocator, traits>::extend_stack()
232		{
233	37972x	if(used_block_count)
234		{
235	37964x	--used_block_count;
236		saved_state* stack_base;
237		saved_state* backup_state;
238	37964x	stack_base = static_cast<saved_state*>(get_mem_block());
239	37964x	backup_state = reinterpret_cast<saved_state>(reinterpret_cast<char>(stack_base)+BOOST_REGEX_BLOCKSIZE);
240	37964x	saved_extra_block* block = reinterpret_cast<saved_extra_block*>(
241	37964x	reinterpret_cast<std::uintptr_t>(backup_state) - sizeof(saved_extra_block));
242	37964x	(void) new (block) saved_extra_block(m_stack_base, m_backup_state);
243	37964x	m_stack_base = stack_base;
244	37964x	m_backup_state = block;
245		}
246		else
247	8x	raise_error(traits_inst, regex_constants::error_stack);
248	37964x	}
249
250		template <class BidiIterator, class Allocator, class traits>
251	4570538x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_matched_paren(int index, const sub_match<BidiIterator>& sub)
252		{
253		//BOOST_REGEX_ASSERT(index);
254	4570538x	saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
255	4570538x	--pmp;
256	4570538x	if(pmp < m_stack_base)
257		{
258	6505x	extend_stack();
259	6505x	pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
260	6505x	--pmp;
261		}
262	4570538x	(void) new (pmp)saved_matched_paren<BidiIterator>(index, sub);
263	4570538x	m_backup_state = pmp;
264	4570538x	}
265
266		template <class BidiIterator, class Allocator, class traits>
267	108360x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_case_change(bool c)
268		{
269		//BOOST_REGEX_ASSERT(index);
270	108360x	saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
271	108360x	--pmp;
272	108360x	if(pmp < m_stack_base)
273		{
274	✗	extend_stack();
275	✗	pmp = static_cast<saved_change_case*>(m_backup_state);
276	✗	--pmp;
277		}
278	108360x	(void) new (pmp)saved_change_case(c);
279	108360x	m_backup_state = pmp;
280	108360x	}
281
282		template <class BidiIterator, class Allocator, class traits>
283	3020252x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_stopper()
284		{
285	3020252x	saved_state* pmp = m_backup_state;
286	3020252x	--pmp;
287	3020252x	if(pmp < m_stack_base)
288		{
289	✗	extend_stack();
290	✗	pmp = m_backup_state;
291	✗	--pmp;
292		}
293	3020252x	(void) new (pmp)saved_state(saved_type_recurse);
294	3020252x	m_backup_state = pmp;
295	3020252x	}
296
297		template <class BidiIterator, class Allocator, class traits>
298	267659x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_assertion(const re_syntax_base* ps, bool positive)
299		{
300	267659x	saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
301	267659x	--pmp;
302	267659x	if(pmp < m_stack_base)
303		{
304	✗	extend_stack();
305	✗	pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
306	✗	--pmp;
307		}
308	267659x	(void) new (pmp)saved_assertion<BidiIterator>(positive, ps, position);
309	267659x	m_backup_state = pmp;
310	267659x	}
311
312		template <class BidiIterator, class Allocator, class traits>
313	1281575x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_alt(const re_syntax_base* ps)
314		{
315	1281575x	saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
316	1281575x	--pmp;
317	1281575x	if(pmp < m_stack_base)
318		{
319	4752x	extend_stack();
320	4752x	pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
321	4752x	--pmp;
322		}
323	1281575x	(void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_alt);
324	1281575x	m_backup_state = pmp;
325	1281575x	}
326
327		template <class BidiIterator, class Allocator, class traits>
328	20376x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_non_greedy_repeat(const re_syntax_base* ps)
329		{
330	20376x	saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
331	20376x	--pmp;
332	20376x	if(pmp < m_stack_base)
333		{
334	✗	extend_stack();
335	✗	pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
336	✗	--pmp;
337		}
338	20376x	(void) new (pmp)saved_position<BidiIterator>(ps, position, saved_state_non_greedy_long_repeat);
339	20376x	m_backup_state = pmp;
340	20376x	}
341
342		template <class BidiIterator, class Allocator, class traits>
343	5751313x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_repeater_count(int i, repeater_count<BidiIterator>** s)
344		{
345	5751313x	saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
346	5751313x	--pmp;
347	5751313x	if(pmp < m_stack_base)
348		{
349	9785x	extend_stack();
350	9777x	pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
351	9777x	--pmp;
352		}
353	5751305x	(void) new (pmp)saved_repeater<BidiIterator>(i, s, position, this->recursion_stack.empty() ? (INT_MIN + 3) : this->recursion_stack.back().idx);
354	5751305x	m_backup_state = pmp;
355	5751305x	}
356
357		template <class BidiIterator, class Allocator, class traits>
358	4107363x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_single_repeat(std::size_t c, const re_repeat* r, BidiIterator last_position, int state_id)
359		{
360	4107363x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
361	4107363x	--pmp;
362	4107363x	if(pmp < m_stack_base)
363		{
364	770x	extend_stack();
365	770x	pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
366	770x	--pmp;
367		}
368	4107363x	(void) new (pmp)saved_single_repeat<BidiIterator>(c, r, last_position, state_id);
369	4107363x	m_backup_state = pmp;
370	4107363x	}
371
372		template <class BidiIterator, class Allocator, class traits>
373	525557x	inline void perl_matcher<BidiIterator, Allocator, traits>::push_recursion(int idx, const re_syntax_base* p, results_type* presults, results_type* presults2)
374		{
375	525557x	saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
376	525557x	--pmp;
377	525557x	if(pmp < m_stack_base)
378		{
379	15338x	extend_stack();
380	15338x	pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
381	15338x	--pmp;
382		}
383	525557x	(void) new (pmp)saved_recursion<results_type>(idx, p, presults, presults2);
384	525557x	m_backup_state = pmp;
385	525557x	}
386
387		template <class BidiIterator, class Allocator, class traits>
388	108360x	bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case()
389		{
390		// change our case sensitivity:
391	108360x	push_case_change(this->icase);
392	108360x	this->icase = static_cast<const re_case*>(pstate)->icase;
393	108360x	pstate = pstate->next.p;
394	108360x	return true;
395		}
396
397		template <class BidiIterator, class Allocator, class traits>
398	8795690x	bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
399		{
400	8795690x	int index = static_cast<const re_brace*>(pstate)->index;
401	8795690x	icase = static_cast<const re_brace*>(pstate)->icase;
402	8795690x	switch(index)
403		{
404	3510996x	case 0:
405	3510996x	pstate = pstate->next.p;
406	3510996x	break;
407	267659x	case -1:
408		case -2:
409		{
410		// forward lookahead assert:
411	267659x	const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
412	267659x	pstate = pstate->next.p->next.p;
413	267659x	push_assertion(next_pstate, index == -1);
414	267659x	break;
415		}
416	336401x	case -3:
417		{
418		// independent sub-expression, currently this is always recursive:
419	336401x	bool old_independent = m_independent;
420	336401x	m_independent = true;
421	336401x	const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
422	336401x	pstate = pstate->next.p->next.p;
423	336401x	bool r = false;
424		#if !defined(BOOST_NO_EXCEPTIONS)
425		try{
426		#endif
427	336401x	r = match_all_states();
428	336401x	if(!r && !m_independent)
429		{
430		// Must be unwinding from a COMMIT/SKIP/PRUNE and the independent
431		// sub failed, need to unwind everything else:
432	6720x	while (m_backup_state->state_id)
433	4320x	unwind(false);
434	2400x	return false;
435		}
436		#if !defined(BOOST_NO_EXCEPTIONS)
437		}
438	✗	catch(...)
439		{
440	✗	pstate = next_pstate;
441		// unwind all pushed states, apart from anything else this
442		// ensures that all the states are correctly destructed
443		// not just the memory freed.
444	✗	while(unwind(true)) {}
445	✗	throw;
446		}
447		#endif
448	334001x	pstate = next_pstate;
449	334001x	m_independent = old_independent;
450		#ifdef BOOST_REGEX_MATCH_EXTRA
451	216x	if(r && (m_match_flags & match_extra))
452		{
453		//
454		// our captures have been stored in *m_presult
455		// we need to unpack them, and insert them
456		// back in the right order when we unwind the stack:
457		//
458	200x	match_results<BidiIterator, Allocator> temp_match(*m_presult);
459		unsigned i;
460	772x	for(i = 0; i < temp_match.size(); ++i)
461	572x	(*m_presult)[i].get_captures().clear();
462		// match everything else:
463		#if !defined(BOOST_NO_EXCEPTIONS)
464		try{
465		#endif
466	200x	r = match_all_states();
467		#if !defined(BOOST_NO_EXCEPTIONS)
468		}
469	✗	catch(...)
470		{
471	✗	pstate = next_pstate;
472		// unwind all pushed states, apart from anything else this
473		// ensures that all the states are correctly destructed
474		// not just the memory freed.
475	✗	while(unwind(true)) {}
476	✗	throw;
477		}
478		#endif
479		// now place the stored captures back:
480	772x	for(i = 0; i < temp_match.size(); ++i)
481		{
482		typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
483	572x	seq& s1 = (*m_presult)[i].get_captures();
484	572x	const seq& s2 = temp_match[i].captures();
485	1144x	s1.insert(
486	1144x	s1.end(),
487		s2.begin(),
488		s2.end());
489		}
490	200x	}
491		#endif
492	334001x	return r;
493		}
494	93920x	case -4:
495		{
496		// conditional expression:
497	93920x	const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
498	93920x	BOOST_REGEX_ASSERT(alt->type == syntax_element_alt);
499	93920x	pstate = alt->next.p;
500	93920x	if(pstate->type == syntax_element_assert_backref)
501		{
502	65792x	if(!match_assert_backref())
503	41668x	pstate = alt->alt.p;
504	65792x	break;
505		}
506		else
507		{
508		// zero width assertion, have to match this recursively:
509	28128x	BOOST_REGEX_ASSERT(pstate->type == syntax_element_startmark);
510	28128x	bool negated = static_cast<const re_brace*>(pstate)->index == -2;
511	28128x	BidiIterator saved_position = position;
512	28128x	const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
513	28128x	pstate = pstate->next.p->next.p;
514		#if !defined(BOOST_NO_EXCEPTIONS)
515		try{
516		#endif
517	28128x	bool r = match_all_states();
518	28128x	position = saved_position;
519	28128x	if(negated)
520	11136x	r = !r;
521	28128x	if(r)
522	11592x	pstate = next_pstate;
523		else
524	16536x	pstate = alt->alt.p;
525		#if !defined(BOOST_NO_EXCEPTIONS)
526		}
527	✗	catch(...)
528		{
529	✗	pstate = next_pstate;
530		// unwind all pushed states, apart from anything else this
531		// ensures that all the states are correctly destructed
532		// not just the memory freed.
533	✗	while(unwind(true)){}
534	✗	throw;
535		}
536		#endif
537	28128x	break;
538		}
539		}
540	2013x	case -5:
541		{
542	2013x	push_matched_paren(0, (*m_presult)[0]);
543	2013x	m_presult->set_first(position, 0, true);
544	2013x	pstate = pstate->next.p;
545	2013x	break;
546		}
547	4584701x	default:
548		{
549	4584701x	BOOST_REGEX_ASSERT(index > 0);
550	4584701x	if((m_match_flags & match_nosubs) == 0)
551		{
552	4568525x	push_matched_paren(index, (*m_presult)[index]);
553	4568525x	m_presult->set_first(position, index);
554		}
555	4584701x	pstate = pstate->next.p;
556	4584701x	break;
557		}
558		}
559	8459289x	return true;
560		}
561
562		template <class BidiIterator, class Allocator, class traits>
563	1597873x	bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
564		{
565		bool take_first, take_second;
566	1597873x	const re_alt* jmp = static_cast<const re_alt*>(pstate);
567
568		// find out which of these two alternatives we need to take:
569	1597873x	if(position == last)
570		{
571	93896x	take_first = jmp->can_be_null & mask_take;
572	93896x	take_second = jmp->can_be_null & mask_skip;
573		}
574		else
575		{
576	1503977x	take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
577	1503977x	take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
578		}
579
580	1597873x	if(take_first)
581		{
582		// we can take the first alternative,
583		// see if we need to push next alternative:
584	1240668x	if(take_second)
585		{
586	852361x	push_alt(jmp->alt.p);
587		}
588	1240668x	pstate = pstate->next.p;
589	1240668x	return true;
590		}
591	357205x	if(take_second)
592		{
593	334563x	pstate = jmp->alt.p;
594	334563x	return true;
595		}
596	22642x	return false; // neither option is possible
597		}
598
599		template <class BidiIterator, class Allocator, class traits>
600	4917842x	bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
601		{
602		#ifdef BOOST_REGEX_MSVC
603		#pragma warning(push)
604		#pragma warning(disable:4127 4244)
605		#endif
606		#ifdef BOOST_BORLANDC
607		#pragma option push -w-8008 -w-8066 -w-8004
608		#endif
609	4917842x	const re_repeat* rep = static_cast<const re_repeat*>(pstate);
610
611		// find out which of these two alternatives we need to take:
612		bool take_first, take_second;
613	4917842x	if(position == last)
614		{
615	421032x	take_first = rep->can_be_null & mask_take;
616	421032x	take_second = rep->can_be_null & mask_skip;
617		}
618		else
619		{
620	4496810x	take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
621	4496810x	take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
622		}
623
624	9835684x	if((m_backup_state->state_id != saved_state_repeater_count)
625	322694x	\|\| (static_cast<saved_repeater<BidiIterator>*>(m_backup_state)->count.get_id() != rep->state_id)
626	5240536x	\|\| (next_count->get_id() != rep->state_id))
627		{
628		// we're moving to a different repeat from the last
629		// one, so set up a counter object:
630	4740650x	push_repeater_count(rep->state_id, &next_count);
631		}
632		//
633		// If we've had at least one repeat already, and the last one
634		// matched the NULL string then set the repeat count to
635		// maximum:
636		//
637	4917834x	next_count->check_null_repeat(position, rep->max);
638
639	4917834x	if(next_count->get_count() < rep->min)
640		{
641		// we must take the repeat:
642	2556822x	if(take_first)
643		{
644		// increase the counter:
645	2474765x	++(*next_count);
646	2474765x	pstate = rep->next.p;
647	2474765x	return true;
648		}
649	82057x	return false;
650		}
651
652	2361012x	bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) \|\| m_independent);
653	2361012x	if(greedy)
654		{
655		// try and take the repeat if we can:
656	2194754x	if((next_count->get_count() < rep->max) && take_first)
657		{
658	981523x	if(take_second)
659		{
660		// store position in case we fail:
661	429214x	push_alt(rep->alt.p);
662		}
663		// increase the counter:
664	981523x	++(*next_count);
665	981523x	pstate = rep->next.p;
666	981523x	return true;
667		}
668	1213231x	else if(take_second)
669		{
670	924145x	pstate = rep->alt.p;
671	924145x	return true;
672		}
673	289086x	return false; // can't take anything, fail...
674		}
675		else // non-greedy
676		{
677		// try and skip the repeat if we can:
678	166258x	if(take_second)
679		{
680	96489x	if((next_count->get_count() < rep->max) && take_first)
681		{
682		// store position in case we fail:
683	20376x	push_non_greedy_repeat(rep->next.p);
684		}
685	96489x	pstate = rep->alt.p;
686	96489x	return true;
687		}
688	69769x	if((next_count->get_count() < rep->max) && take_first)
689		{
690		// increase the counter:
691	59281x	++(*next_count);
692	59281x	pstate = rep->next.p;
693	59281x	return true;
694		}
695		}
696	10488x	return false;
697		#ifdef BOOST_BORLANDC
698		#pragma option pop
699		#endif
700		#ifdef BOOST_REGEX_MSVC
701		#pragma warning(pop)
702		#endif
703		}
704
705		template <class BidiIterator, class Allocator, class traits>
706	3080628x	bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
707		{
708	3080628x	std::size_t count = 0;
709	3080628x	const re_repeat* rep = static_cast<const re_repeat*>(pstate);
710	3080628x	re_syntax_base* psingle = rep->next.p;
711		// match compulsory repeats first:
712	3107207x	while(count < rep->min)
713		{
714	32772x	pstate = psingle;
715	32772x	if(!match_wild())
716	6193x	return false;
717	26579x	++count;
718		}
719	3074435x	bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) \|\| m_independent);
720	3074435x	if(greedy)
721		{
722		// repeat for as long as we can:
723	172713926x	while(count < rep->max)
724		{
725	172711238x	pstate = psingle;
726	172711238x	if(!match_wild())
727	2914235x	break;
728	169797003x	++count;
729		}
730		// remember where we got to if this is a leading repeat:
731	2916923x	if((rep->leading) && (count < rep->max))
732	6193x	restart = position;
733		// push backtrack info if available:
734	2916923x	if(count - rep->min)
735	2888411x	push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
736		// jump to next state:
737	2916923x	pstate = rep->alt.p;
738	2916923x	return true;
739		}
740		else
741		{
742		// non-greedy, push state and return true if we can skip:
743	157512x	if(count < rep->max)
744	157512x	push_single_repeat(count, rep, position, saved_state_rep_slow_dot);
745	157512x	pstate = rep->alt.p;
746	157512x	return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
747		}
748		}
749
750		template <class BidiIterator, class Allocator, class traits>
751	3427242x	bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
752		{
753	3427242x	if(m_match_flags & match_not_dot_null)
754	18456x	return match_dot_repeat_slow();
755	3408786x	if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
756	3053232x	return match_dot_repeat_slow();
757
758	355554x	const re_repeat* rep = static_cast<const re_repeat*>(pstate);
759	355554x	bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) \|\| m_independent);
760	711108x	std::size_t count = static_cast<std::size_t>((std::min)(static_cast<std::size_t>(std::distance(position, last)), greedy ? rep->max : rep->min));
761	355554x	if(rep->min > count)
762		{
763	5328x	position = last;
764	5328x	return false; // not enough text left to match
765		}
766	350226x	std::advance(position, count);
767
768	350226x	if(greedy)
769		{
770	317745x	if((rep->leading) && (count < rep->max))
771	14424x	restart = position;
772		// push backtrack info if available:
773	317745x	if(count - rep->min)
774	174652x	push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
775		// jump to next state:
776	317745x	pstate = rep->alt.p;
777	317745x	return true;
778		}
779		else
780		{
781		// non-greedy, push state and return true if we can skip:
782	32481x	if(count < rep->max)
783	32337x	push_single_repeat(count, rep, position, saved_state_rep_fast_dot);
784	32481x	pstate = rep->alt.p;
785	32481x	return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
786		}
787		}
788
789		template <class BidiIterator, class Allocator, class traits>
790	577865x	bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
791		{
792		#ifdef BOOST_REGEX_MSVC
793		#pragma warning(push)
794		#pragma warning(disable:4127)
795		#endif
796		#ifdef BOOST_BORLANDC
797		#pragma option push -w-8008 -w-8066 -w-8004
798		#endif
799	577865x	const re_repeat* rep = static_cast<const re_repeat*>(pstate);
800	577865x	BOOST_REGEX_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
801	577865x	const char_type what = reinterpret_cast<const char_type>(static_cast<const re_literal*>(rep->next.p) + 1);
802	577865x	std::size_t count = 0;
803		//
804		// start by working out how much we can skip:
805		//
806	577865x	bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) \|\| m_independent);
807	577865x	std::size_t desired = greedy ? rep->max : rep->min;
808		if(::boost::is_random_access_iterator<BidiIterator>::value)
809		{
810	479895x	BidiIterator end = position;
811		// Move end forward by "desired", preferably without using distance or advance if we can
812		// as these can be slow for some iterator types.
813	654743x	std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
814	479895x	if(desired >= len)
815	377822x	end = last;
816		else
817		std::advance(end, desired);
818	479895x	BidiIterator origin(position);
819	114319925x	while((position != end) && (traits_inst.translate(*position, icase) == what))
820		{
821	113840030x	++position;
822		}
823	525554x	count = (unsigned)std::distance(origin, position);
824		}
825		else
826		{
827	165555x	while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
828		{
829	67585x	++position;
830	67585x	++count;
831		}
832		}
833
834	577865x	if(count < rep->min)
835	232208x	return false;
836
837	345657x	if(greedy)
838		{
839	271636x	if((rep->leading) && (count < rep->max))
840	60998x	restart = position;
841		// push backtrack info if available:
842	271636x	if(count - rep->min)
843	138321x	push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
844		// jump to next state:
845	271636x	pstate = rep->alt.p;
846	271636x	return true;
847		}
848		else
849		{
850		// non-greedy, push state and return true if we can skip:
851	74021x	if(count < rep->max)
852	73637x	push_single_repeat(count, rep, position, saved_state_rep_char);
853	74021x	pstate = rep->alt.p;
854	74021x	return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
855		}
856		#ifdef BOOST_BORLANDC
857		#pragma option pop
858		#endif
859		#ifdef BOOST_REGEX_MSVC
860		#pragma warning(pop)
861		#endif
862		}
863
864		template <class BidiIterator, class Allocator, class traits>
865	816089x	bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
866		{
867		#ifdef BOOST_REGEX_MSVC
868		#pragma warning(push)
869		#pragma warning(disable:4127)
870		#endif
871		#ifdef BOOST_BORLANDC
872		#pragma option push -w-8008 -w-8066 -w-8004
873		#endif
874	816089x	const re_repeat* rep = static_cast<const re_repeat*>(pstate);
875	816089x	const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
876	816089x	std::size_t count = 0;
877		//
878		// start by working out how much we can skip:
879		//
880	816089x	bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) \|\| m_independent);
881	816089x	std::size_t desired = greedy ? rep->max : rep->min;
882		if(::boost::is_random_access_iterator<BidiIterator>::value)
883		{
884	816089x	BidiIterator end = position;
885		// Move end forward by "desired", preferably without using distance or advance if we can
886		// as these can be slow for some iterator types.
887	991731x	std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
888	816089x	if(desired >= len)
889	672447x	end = last;
890		else
891		std::advance(end, desired);
892	816089x	BidiIterator origin(position);
893	3105715x	while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
894		{
895	2289626x	++position;
896		}
897	849240x	count = (unsigned)std::distance(origin, position);
898		}
899		else
900		{
901	✗	while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
902		{
903	✗	++position;
904	✗	++count;
905		}
906		}
907
908	816089x	if(count < rep->min)
909	196345x	return false;
910
911	619744x	if(greedy)
912		{
913	497170x	if((rep->leading) && (count < rep->max))
914	35179x	restart = position;
915		// push backtrack info if available:
916	497170x	if(count - rep->min)
917	185590x	push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
918		// jump to next state:
919	497170x	pstate = rep->alt.p;
920	497170x	return true;
921		}
922		else
923		{
924		// non-greedy, push state and return true if we can skip:
925	122574x	if(count < rep->max)
926	122052x	push_single_repeat(count, rep, position, saved_state_rep_short_set);
927	122574x	pstate = rep->alt.p;
928	122574x	return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
929		}
930		#ifdef BOOST_BORLANDC
931		#pragma option pop
932		#endif
933		#ifdef BOOST_REGEX_MSVC
934		#pragma warning(pop)
935		#endif
936		}
937
938		template <class BidiIterator, class Allocator, class traits>
939	1007543x	bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
940		{
941		#ifdef BOOST_REGEX_MSVC
942		#pragma warning(push)
943		#pragma warning(disable:4127)
944		#endif
945		#ifdef BOOST_BORLANDC
946		#pragma option push -w-8008 -w-8066 -w-8004
947		#endif
948		typedef typename traits::char_class_type m_type;
949	1007543x	const re_repeat* rep = static_cast<const re_repeat*>(pstate);
950	1007543x	const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate->next.p);
951	1007543x	std::size_t count = 0;
952		//
953		// start by working out how much we can skip:
954		//
955	1007543x	bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) \|\| m_independent);
956	1007543x	std::size_t desired = greedy ? rep->max : rep->min;
957		if(::boost::is_random_access_iterator<BidiIterator>::value)
958		{
959	853785x	BidiIterator end = position;
960		// Move end forward by "desired", preferably without using distance or advance if we can
961		// as these can be slow for some iterator types.
962	1032345x	std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : std::distance(position, last);
963	853785x	if(desired >= len)
964	711333x	end = last;
965		else
966		std::advance(end, desired);
967	853785x	BidiIterator origin(position);
968	1567440x	while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
969		{
970	713655x	++position;
971		}
972	885249x	count = (unsigned)std::distance(origin, position);
973		}
974		else
975		{
976	317776x	while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
977		{
978	164018x	++position;
979	164018x	++count;
980		}
981		}
982
983	1007543x	if(count < rep->min)
984	242772x	return false;
985
986	764771x	if(greedy)
987		{
988	644015x	if((rep->leading) && (count < rep->max))
989	47655x	restart = position;
990		// push backtrack info if available:
991	644015x	if(count - rep->min)
992	214599x	push_single_repeat(count, rep, position, saved_state_greedy_single_repeat);
993		// jump to next state:
994	644015x	pstate = rep->alt.p;
995	644015x	return true;
996		}
997		else
998		{
999		// non-greedy, push state and return true if we can skip:
1000	120756x	if(count < rep->max)
1001	120252x	push_single_repeat(count, rep, position, saved_state_rep_long_set);
1002	120756x	pstate = rep->alt.p;
1003	120756x	return (position == last) ? (rep->can_be_null & mask_skip) : can_start(*position, rep->_map, mask_skip);
1004		}
1005		#ifdef BOOST_BORLANDC
1006		#pragma option pop
1007		#endif
1008		#ifdef BOOST_REGEX_MSVC
1009		#pragma warning(pop)
1010		#endif
1011		}
1012
1013		template <class BidiIterator, class Allocator, class traits>
1014	510449x	bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
1015		{
1016	510449x	BOOST_REGEX_ASSERT(pstate->type == syntax_element_recurse);
1017		//
1018		// See if we've seen this recursion before at this location, if we have then
1019		// we need to prevent infinite recursion:
1020		//
1021	511793x	for(typename std::vector<recursion_info<results_type> >::reverse_iterator i = recursion_stack.rbegin(); i != recursion_stack.rend(); ++i)
1022		{
1023	402580x	if(i->idx == static_cast<const re_brace>(static_cast<const re_jump>(pstate)->alt.p)->index)
1024		{
1025	401236x	if(i->location_of_start == position)
1026	119x	return false;
1027	401117x	break;
1028		}
1029		}
1030		//
1031		// Backup call stack:
1032		//
1033	510330x	push_recursion_pop();
1034		//
1035		// Set new call stack:
1036		//
1037	510330x	if(recursion_stack.capacity() == 0)
1038		{
1039	66109x	recursion_stack.reserve(50);
1040		}
1041	510330x	recursion_stack.push_back(recursion_info<results_type>());
1042	510330x	recursion_stack.back().preturn_address = pstate->next.p;
1043	510330x	recursion_stack.back().results = *m_presult;
1044	510330x	pstate = static_cast<const re_jump*>(pstate)->alt.p;
1045	510330x	recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
1046	510330x	recursion_stack.back().location_of_start = position;
1047		//if(static_cast<const re_recurse*>(pstate)->state_id > 0)
1048		{
1049	510330x	push_repeater_count(-(2 + static_cast<const re_brace*>(pstate)->index), &next_count);
1050		}
1051
1052	510330x	return true;
1053		}
1054
1055		template <class BidiIterator, class Allocator, class traits>
1056	6040400x	bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
1057		{
1058	6040400x	int index = static_cast<const re_brace*>(pstate)->index;
1059	6040400x	icase = static_cast<const re_brace*>(pstate)->icase;
1060	6040400x	if(index > 0)
1061		{
1062	4672995x	if((m_match_flags & match_nosubs) == 0)
1063		{
1064	4652283x	m_presult->set_second(position, index);
1065		}
1066	4672995x	if(!recursion_stack.empty())
1067		{
1068	880493x	if(index == recursion_stack.back().idx)
1069		{
1070	500333x	pstate = recursion_stack.back().preturn_address;
1071	500333x	*m_presult = recursion_stack.back().results;
1072	500333x	push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, m_presult, &recursion_stack.back().results);
1073	500333x	recursion_stack.pop_back();
1074	500333x	push_repeater_count(-(2 + index), &next_count);
1075		}
1076		}
1077		}
1078	1367405x	else if((index < 0) && (index != -4))
1079		{
1080		// matched forward lookahead:
1081	340567x	pstate = 0;
1082	340567x	return true;
1083		}
1084	5699833x	pstate = pstate->next.p;
1085	5699833x	return true;
1086		}
1087
1088		template <class BidiIterator, class Allocator, class traits>
1089	1132042x	bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
1090		{
1091	1132042x	if(!recursion_stack.empty())
1092		{
1093	25224x	BOOST_REGEX_ASSERT(0 == recursion_stack.back().idx);
1094	25224x	pstate = recursion_stack.back().preturn_address;
1095	25224x	push_recursion(recursion_stack.back().idx, recursion_stack.back().preturn_address, m_presult, &recursion_stack.back().results);
1096	25224x	*m_presult = recursion_stack.back().results;
1097	25224x	recursion_stack.pop_back();
1098	25224x	return true;
1099		}
1100	1106818x	if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
1101	5424x	return false;
1102	1101394x	if((m_match_flags & match_all) && (position != last))
1103	16787x	return false;
1104	1084607x	if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
1105	79884x	return false;
1106	1004723x	m_presult->set_second(position);
1107	1004723x	pstate = 0;
1108	1004723x	m_has_found_match = true;
1109	1004723x	if((m_match_flags & match_posix) == match_posix)
1110		{
1111	304674x	m_result.maybe_assign(*m_presult);
1112	304674x	if((m_match_flags & match_any) == 0)
1113	290466x	return false;
1114		}
1115		#ifdef BOOST_REGEX_MATCH_EXTRA
1116	32x	if(match_extra & m_match_flags)
1117		{
1118	140x	for(unsigned i = 0; i < m_presult->size(); ++i)
1119	108x	if((*m_presult)[i].matched)
1120	96x	((m_presult)[i]).get_captures().push_back((m_presult)[i]);
1121		}
1122		#endif
1123	714257x	return true;
1124		}
1125
1126		template <class BidiIterator, class Allocator, class traits>
1127	24269x	bool perl_matcher<BidiIterator, Allocator, traits>::match_commit()
1128		{
1129		// Ideally we would just junk all the states that are on the stack,
1130		// however we might not unwind correctly in that case, so for now,
1131		// just mark that we don't backtrack into whatever is left (or rather
1132		// we'll unwind it unconditionally without pausing to try other matches).
1133
1134	24269x	switch(static_cast<const re_commit*>(pstate)->action)
1135		{
1136	5208x	case commit_commit:
1137	5208x	restart = last;
1138	5208x	break;
1139	16301x	case commit_skip:
1140	16301x	if(base != position)
1141		{
1142	15819x	restart = position;
1143		// Have to decrement restart since it will get incremented again later:
1144	15819x	--restart;
1145		}
1146	16301x	break;
1147	2760x	case commit_prune:
1148	2760x	break;
1149		}
1150
1151	24269x	saved_state* pmp = m_backup_state;
1152	24269x	--pmp;
1153	24269x	if(pmp < m_stack_base)
1154		{
1155	✗	extend_stack();
1156	✗	pmp = m_backup_state;
1157	✗	--pmp;
1158		}
1159	24269x	(void) new (pmp)saved_state(16);
1160	24269x	m_backup_state = pmp;
1161	24269x	pstate = pstate->next.p;
1162	24269x	return true;
1163		}
1164
1165		template <class BidiIterator, class Allocator, class traits>
1166	8064x	bool perl_matcher<BidiIterator, Allocator, traits>::match_then()
1167		{
1168		// Just leave a mark that we need to skip to next alternative:
1169	8064x	saved_state* pmp = m_backup_state;
1170	8064x	--pmp;
1171	8064x	if(pmp < m_stack_base)
1172		{
1173	✗	extend_stack();
1174	✗	pmp = m_backup_state;
1175	✗	--pmp;
1176		}
1177	8064x	(void) new (pmp)saved_state(17);
1178	8064x	m_backup_state = pmp;
1179	8064x	pstate = pstate->next.p;
1180	8064x	return true;
1181		}
1182
1183		template <class BidiIterator, class Allocator, class traits>
1184	6846x	bool perl_matcher<BidiIterator, Allocator, traits>::skip_until_paren(int index, bool have_match)
1185		{
1186	35927x	while(pstate)
1187		{
1188	35927x	if(pstate->type == syntax_element_endmark)
1189		{
1190	8237x	if(static_cast<const re_brace*>(pstate)->index == index)
1191		{
1192	3265x	if(have_match)
1193	1872x	return this->match_endmark();
1194	1393x	pstate = pstate->next.p;
1195	1393x	return true;
1196		}
1197		else
1198		{
1199		// Unenclosed closing ), occurs when (*ACCEPT) is inside some other
1200		// parenthesis which may or may not have other side effects associated with it.
1201	4972x	const re_syntax_base* sp = pstate;
1202	4972x	match_endmark();
1203	4972x	if(!pstate)
1204		{
1205	890x	unwind(true);
1206		// unwind may leave pstate NULL if we've unwound a forward lookahead, in which
1207		// case just move to the next state and keep looking...
1208	890x	if (!pstate)
1209	2x	pstate = sp->next.p;
1210		}
1211		}
1212	4972x	continue;
1213	4972x	}
1214	27690x	else if(pstate->type == syntax_element_match)
1215	3581x	return true;
1216	24109x	else if(pstate->type == syntax_element_startmark)
1217		{
1218	1396x	int idx = static_cast<const re_brace*>(pstate)->index;
1219	1396x	if(idx > 0)
1220	1393x	match_startmark();
1221		else
1222	3x	pstate = pstate->next.p;
1223	1396x	skip_until_paren(idx, false);
1224	1396x	continue;
1225	1396x	}
1226	22713x	pstate = pstate->next.p;
1227		}
1228	✗	return true;
1229		}
1230
1231		/****************************************************************************
1232
1233		Unwind and associated procedures follow, these perform what normal stack
1234		unwinding does in the recursive implementation.
1235
1236		****************************************************************************/
1237
1238		template <class BidiIterator, class Allocator, class traits>
1239	38981374x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind(bool have_match)
1240		{
1241		static unwind_proc_type const s_unwind_table[19] =
1242		{
1243		&perl_matcher<BidiIterator, Allocator, traits>::unwind_end,
1244		&perl_matcher<BidiIterator, Allocator, traits>::unwind_paren,
1245		&perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper,
1246		&perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion,
1247		&perl_matcher<BidiIterator, Allocator, traits>::unwind_alt,
1248		&perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter,
1249		&perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block,
1250		&perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat,
1251		&perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat,
1252		&perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat,
1253		&perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat,
1254		&perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat,
1255		&perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat,
1256		&perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat,
1257		&perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion,
1258		&perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop,
1259		&perl_matcher<BidiIterator, Allocator, traits>::unwind_commit,
1260		&perl_matcher<BidiIterator, Allocator, traits>::unwind_then,
1261		&perl_matcher<BidiIterator, Allocator, traits>::unwind_case,
1262		};
1263
1264	38981374x	m_recursive_result = have_match;
1265	38981374x	m_unwound_lookahead = false;
1266	38981374x	m_unwound_alt = false;
1267		unwind_proc_type unwinder;
1268		bool cont;
1269		//
1270		// keep unwinding our stack until we have something to do:
1271		//
1272	55059665x	do
1273		{
1274	55059665x	unwinder = s_unwind_table[m_backup_state->state_id];
1275	55059665x	cont = (this->*unwinder)(m_recursive_result);
1276		}while(cont);
1277		//
1278		// return true if we have more states to try:
1279		//
1280	38981374x	return pstate ? true : false;
1281		}
1282
1283		template <class BidiIterator, class Allocator, class traits>
1284	2403x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_end(bool)
1285		{
1286	2403x	pstate = 0; // nothing left to search
1287	2403x	return false; // end of stack nothing more to search
1288		}
1289
1290		template <class BidiIterator, class Allocator, class traits>
1291	108360x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_case(bool)
1292		{
1293	108360x	saved_change_case* pmp = static_cast<saved_change_case*>(m_backup_state);
1294	108360x	icase = pmp->icase;
1295	108360x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1296	108360x	m_backup_state = pmp;
1297	108360x	return true;
1298		}
1299
1300		template <class BidiIterator, class Allocator, class traits>
1301	4570538x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_paren(bool have_match)
1302		{
1303	4570538x	saved_matched_paren<BidiIterator>* pmp = static_cast<saved_matched_paren<BidiIterator>*>(m_backup_state);
1304		// restore previous values if no match was found:
1305	4570538x	if(!have_match)
1306		{
1307	3750368x	m_presult->set_first(pmp->sub.first, pmp->index, pmp->index == 0);
1308	3750368x	m_presult->set_second(pmp->sub.second, pmp->index, pmp->sub.matched, pmp->index == 0);
1309		}
1310		#ifdef BOOST_REGEX_MATCH_EXTRA
1311		//
1312		// we have a match, push the capture information onto the stack:
1313		//
1314	316x	else if(pmp->sub.matched && (match_extra & m_match_flags))
1315	252x	((*m_presult)[pmp->index]).get_captures().push_back(pmp->sub);
1316		#endif
1317		// unwind stack:
1318	4570538x	m_backup_state = pmp+1;
1319	4570538x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1320	4570538x	return true; // keep looking
1321		}
1322
1323		template <class BidiIterator, class Allocator, class traits>
1324	3020252x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_stopper(bool)
1325		{
1326	3020252x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1327	3020252x	pstate = 0; // nothing left to search
1328	3020252x	return false; // end of stack nothing more to search
1329		}
1330
1331		template <class BidiIterator, class Allocator, class traits>
1332	267659x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_assertion(bool r)
1333		{
1334	267659x	saved_assertion<BidiIterator>* pmp = static_cast<saved_assertion<BidiIterator>*>(m_backup_state);
1335	267659x	pstate = pmp->pstate;
1336	267659x	position = pmp->position;
1337	267659x	bool result = (r == pmp->positive);
1338	267659x	m_recursive_result = pmp->positive ? r : !r;
1339	267659x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1340	267659x	m_backup_state = pmp;
1341	267659x	m_unwound_lookahead = true;
1342	267659x	return !result; // return false if the assertion was matched to stop search.
1343	87126x	}
1344
1345		template <class BidiIterator, class Allocator, class traits>
1346	1281575x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_alt(bool r)
1347		{
1348	1281575x	saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1349	1281575x	if(!r)
1350		{
1351	637114x	pstate = pmp->pstate;
1352	637114x	position = pmp->position;
1353		}
1354	1281575x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1355	1281575x	m_backup_state = pmp;
1356	1281575x	m_unwound_alt = !r;
1357	1281575x	return r;
1358		}
1359
1360		template <class BidiIterator, class Allocator, class traits>
1361	5751305x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_repeater_counter(bool)
1362		{
1363	5751305x	saved_repeater<BidiIterator>* pmp = static_cast<saved_repeater<BidiIterator>*>(m_backup_state);
1364	5751305x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1365	5751305x	m_backup_state = pmp;
1366	5751305x	return true; // keep looking
1367		}
1368
1369		template <class BidiIterator, class Allocator, class traits>
1370	37964x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_extra_block(bool)
1371		{
1372	37964x	++used_block_count;
1373	37964x	saved_extra_block* pmp = static_cast<saved_extra_block*>(m_backup_state);
1374	37964x	void* condemmed = m_stack_base;
1375	37964x	m_stack_base = pmp->base;
1376	37964x	m_backup_state = pmp->end;
1377	37964x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp);
1378	37964x	put_mem_block(condemmed);
1379	37964x	return true; // keep looking
1380		}
1381
1382		template <class BidiIterator, class Allocator, class traits>
1383	4107363x	inline void perl_matcher<BidiIterator, Allocator, traits>::destroy_single_repeat()
1384		{
1385	4107363x	saved_single_repeat<BidiIterator>* p = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1386	4107363x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(p++);
1387	4107363x	m_backup_state = p;
1388	4107363x	}
1389
1390		template <class BidiIterator, class Allocator, class traits>
1391	36324925x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_greedy_single_repeat(bool r)
1392		{
1393	36324925x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1394
1395		// if we have a match, just discard this state:
1396	36324925x	if(r)
1397		{
1398	352378x	destroy_single_repeat();
1399	352378x	return true;
1400		}
1401
1402	35972547x	const re_repeat* rep = pmp->rep;
1403	35972547x	std::size_t count = pmp->count;
1404	35972547x	BOOST_REGEX_ASSERT(rep->next.p != 0);
1405	35972547x	BOOST_REGEX_ASSERT(rep->alt.p != 0);
1406
1407	35972547x	count -= rep->min;
1408
1409	35972547x	if((m_match_flags & match_partial) && (position == last))
1410	13575x	m_has_partial_match = true;
1411
1412	35972547x	BOOST_REGEX_ASSERT(count);
1413	35972547x	position = pmp->last_position;
1414
1415		// backtrack till we can skip out:
1416		do
1417		{
1418	286165795x	--position;
1419	286165795x	--count;
1420	286165795x	++state_count;
1421	286165795x	}while(count && !can_start(*position, rep->_map, mask_skip));
1422
1423		// if we've hit base, destroy this state:
1424	35972547x	if(count == 0)
1425		{
1426	3249195x	destroy_single_repeat();
1427	3249195x	if(!can_start(*position, rep->_map, mask_skip))
1428	2936915x	return true;
1429		}
1430		else
1431		{
1432	32723352x	pmp->count = count + rep->min;
1433	32723352x	pmp->last_position = position;
1434		}
1435	33035632x	pstate = rep->alt.p;
1436	33035632x	return false;
1437		}
1438
1439		template <class BidiIterator, class Allocator, class traits>
1440	2155392x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_slow_dot_repeat(bool r)
1441		{
1442	2155392x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1443
1444		// if we have a match, just discard this state:
1445	2155392x	if(r)
1446		{
1447	6648x	destroy_single_repeat();
1448	6648x	return true;
1449		}
1450
1451	2148744x	const re_repeat* rep = pmp->rep;
1452	2148744x	std::size_t count = pmp->count;
1453	2148744x	BOOST_REGEX_ASSERT(rep->type == syntax_element_dot_rep);
1454	2148744x	BOOST_REGEX_ASSERT(rep->next.p != 0);
1455	2148744x	BOOST_REGEX_ASSERT(rep->alt.p != 0);
1456	2148744x	BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_wild);
1457
1458	2148744x	BOOST_REGEX_ASSERT(count < rep->max);
1459	2148744x	pstate = rep->next.p;
1460	2148744x	position = pmp->last_position;
1461
1462	2148744x	if(position != last)
1463		{
1464		// wind forward until we can skip out of the repeat:
1465		do
1466		{
1467	9358536x	if(!match_wild())
1468		{
1469		// failed repeat match, discard this state and look for another:
1470	144840x	destroy_single_repeat();
1471	144840x	return true;
1472		}
1473	9213696x	++count;
1474	9213696x	++state_count;
1475	9213696x	pstate = rep->next.p;
1476	9213696x	}while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1477		}
1478	2003904x	if(position == last)
1479		{
1480		// can't repeat any more, remove the pushed state:
1481	4368x	destroy_single_repeat();
1482	4368x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1483	1056x	m_has_partial_match = true;
1484	4368x	if(0 == (rep->can_be_null & mask_skip))
1485	3768x	return true;
1486		}
1487	1999536x	else if(count == rep->max)
1488		{
1489		// can't repeat any more, remove the pushed state:
1490	1656x	destroy_single_repeat();
1491	1656x	if(!can_start(*position, rep->_map, mask_skip))
1492	600x	return true;
1493		}
1494		else
1495		{
1496	1997880x	pmp->count = count;
1497	1997880x	pmp->last_position = position;
1498		}
1499	1999536x	pstate = rep->alt.p;
1500	1999536x	return false;
1501		}
1502
1503		template <class BidiIterator, class Allocator, class traits>
1504	61263x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_fast_dot_repeat(bool r)
1505		{
1506	61263x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1507
1508		// if we have a match, just discard this state:
1509	61263x	if(r)
1510		{
1511	24561x	destroy_single_repeat();
1512	24561x	return true;
1513		}
1514
1515	36702x	const re_repeat* rep = pmp->rep;
1516	36702x	std::size_t count = pmp->count;
1517
1518	36702x	BOOST_REGEX_ASSERT(count < rep->max);
1519	36702x	position = pmp->last_position;
1520	36702x	if(position != last)
1521		{
1522
1523		// wind forward until we can skip out of the repeat:
1524		do
1525		{
1526	75604x	++position;
1527	75604x	++count;
1528	75604x	++state_count;
1529	75604x	}while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1530		}
1531
1532		// remember where we got to if this is a leading repeat:
1533	36702x	if((rep->leading) && (count < rep->max))
1534	8016x	restart = position;
1535	36702x	if(position == last)
1536		{
1537		// can't repeat any more, remove the pushed state:
1538	6336x	destroy_single_repeat();
1539	6336x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1540	1416x	m_has_partial_match = true;
1541	6336x	if(0 == (rep->can_be_null & mask_skip))
1542	2712x	return true;
1543		}
1544	30366x	else if(count == rep->max)
1545		{
1546		// can't repeat any more, remove the pushed state:
1547	1440x	destroy_single_repeat();
1548	1440x	if(!can_start(*position, rep->_map, mask_skip))
1549	528x	return true;
1550		}
1551		else
1552		{
1553	28926x	pmp->count = count;
1554	28926x	pmp->last_position = position;
1555		}
1556	33462x	pstate = rep->alt.p;
1557	33462x	return false;
1558		}
1559
1560		template <class BidiIterator, class Allocator, class traits>
1561	85733x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_char_repeat(bool r)
1562		{
1563	85733x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1564
1565		// if we have a match, just discard this state:
1566	85733x	if(r)
1567		{
1568	53861x	destroy_single_repeat();
1569	53861x	return true;
1570		}
1571
1572	31872x	const re_repeat* rep = pmp->rep;
1573	31872x	std::size_t count = pmp->count;
1574	31872x	pstate = rep->next.p;
1575	31872x	const char_type what = reinterpret_cast<const char_type>(static_cast<const re_literal*>(pstate) + 1);
1576	31872x	position = pmp->last_position;
1577
1578	31872x	BOOST_REGEX_ASSERT(rep->type == syntax_element_char_rep);
1579	31872x	BOOST_REGEX_ASSERT(rep->next.p != 0);
1580	31872x	BOOST_REGEX_ASSERT(rep->alt.p != 0);
1581	31872x	BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_literal);
1582	31872x	BOOST_REGEX_ASSERT(count < rep->max);
1583
1584	31872x	if(position != last)
1585		{
1586		// wind forward until we can skip out of the repeat:
1587		do
1588		{
1589	43128x	if(traits_inst.translate(*position, icase) != what)
1590		{
1591		// failed repeat match, discard this state and look for another:
1592	5304x	destroy_single_repeat();
1593	5304x	return true;
1594		}
1595	37824x	++count;
1596	37824x	++ position;
1597	37824x	++state_count;
1598	37824x	pstate = rep->next.p;
1599	37824x	}while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1600		}
1601		// remember where we got to if this is a leading repeat:
1602	26568x	if((rep->leading) && (count < rep->max))
1603	8808x	restart = position;
1604	26568x	if(position == last)
1605		{
1606		// can't repeat any more, remove the pushed state:
1607	10632x	destroy_single_repeat();
1608	10632x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1609	1368x	m_has_partial_match = true;
1610	10632x	if(0 == (rep->can_be_null & mask_skip))
1611	3480x	return true;
1612		}
1613	15936x	else if(count == rep->max)
1614		{
1615		// can't repeat any more, remove the pushed state:
1616	3840x	destroy_single_repeat();
1617	3840x	if(!can_start(*position, rep->_map, mask_skip))
1618	1536x	return true;
1619		}
1620		else
1621		{
1622	12096x	pmp->count = count;
1623	12096x	pmp->last_position = position;
1624		}
1625	21552x	pstate = rep->alt.p;
1626	21552x	return false;
1627		}
1628
1629		template <class BidiIterator, class Allocator, class traits>
1630	152112x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_short_set_repeat(bool r)
1631		{
1632	152112x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1633
1634		// if we have a match, just discard this state:
1635	152112x	if(r)
1636		{
1637	13956x	destroy_single_repeat();
1638	13956x	return true;
1639		}
1640
1641	138156x	const re_repeat* rep = pmp->rep;
1642	138156x	std::size_t count = pmp->count;
1643	138156x	pstate = rep->next.p;
1644	138156x	const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
1645	138156x	position = pmp->last_position;
1646
1647	138156x	BOOST_REGEX_ASSERT(rep->type == syntax_element_short_set_rep);
1648	138156x	BOOST_REGEX_ASSERT(rep->next.p != 0);
1649	138156x	BOOST_REGEX_ASSERT(rep->alt.p != 0);
1650	138156x	BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_set);
1651	138156x	BOOST_REGEX_ASSERT(count < rep->max);
1652
1653	138156x	if(position != last)
1654		{
1655		// wind forward until we can skip out of the repeat:
1656		do
1657		{
1658	161736x	if(!map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
1659		{
1660		// failed repeat match, discard this state and look for another:
1661	89016x	destroy_single_repeat();
1662	89016x	return true;
1663		}
1664	72720x	++count;
1665	72720x	++ position;
1666	72720x	++state_count;
1667	72720x	pstate = rep->next.p;
1668	72720x	}while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1669		}
1670		// remember where we got to if this is a leading repeat:
1671	49140x	if((rep->leading) && (count < rep->max))
1672	1536x	restart = position;
1673	49140x	if(position == last)
1674		{
1675		// can't repeat any more, remove the pushed state:
1676	17148x	destroy_single_repeat();
1677	17148x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1678	576x	m_has_partial_match = true;
1679	17148x	if(0 == (rep->can_be_null & mask_skip))
1680	4068x	return true;
1681		}
1682	31992x	else if(count == rep->max)
1683		{
1684		// can't repeat any more, remove the pushed state:
1685	1932x	destroy_single_repeat();
1686	1932x	if(!can_start(*position, rep->_map, mask_skip))
1687	828x	return true;
1688		}
1689		else
1690		{
1691	30060x	pmp->count = count;
1692	30060x	pmp->last_position = position;
1693		}
1694	44244x	pstate = rep->alt.p;
1695	44244x	return false;
1696		}
1697
1698		template <class BidiIterator, class Allocator, class traits>
1699	138672x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_long_set_repeat(bool r)
1700		{
1701		typedef typename traits::char_class_type m_type;
1702	138672x	saved_single_repeat<BidiIterator>* pmp = static_cast<saved_single_repeat<BidiIterator>*>(m_backup_state);
1703
1704		// if we have a match, just discard this state:
1705	138672x	if(r)
1706		{
1707	14796x	destroy_single_repeat();
1708	14796x	return true;
1709		}
1710
1711	123876x	const re_repeat* rep = pmp->rep;
1712	123876x	std::size_t count = pmp->count;
1713	123876x	pstate = rep->next.p;
1714	123876x	const re_set_long<m_type>* set = static_cast<const re_set_long<m_type>*>(pstate);
1715	123876x	position = pmp->last_position;
1716
1717	123876x	BOOST_REGEX_ASSERT(rep->type == syntax_element_long_set_rep);
1718	123876x	BOOST_REGEX_ASSERT(rep->next.p != 0);
1719	123876x	BOOST_REGEX_ASSERT(rep->alt.p != 0);
1720	123876x	BOOST_REGEX_ASSERT(rep->next.p->type == syntax_element_long_set);
1721	123876x	BOOST_REGEX_ASSERT(count < rep->max);
1722
1723	123876x	if(position != last)
1724		{
1725		// wind forward until we can skip out of the repeat:
1726		do
1727		{
1728	149976x	if(position == re_is_set_member(position, last, set, re.get_data(), icase))
1729		{
1730		// failed repeat match, discard this state and look for another:
1731	86424x	destroy_single_repeat();
1732	86424x	return true;
1733		}
1734	63552x	++position;
1735	63552x	++count;
1736	63552x	++state_count;
1737	63552x	pstate = rep->next.p;
1738	63552x	}while((count < rep->max) && (position != last) && !can_start(*position, rep->_map, mask_skip));
1739		}
1740		// remember where we got to if this is a leading repeat:
1741	37452x	if((rep->leading) && (count < rep->max))
1742	1944x	restart = position;
1743	37452x	if(position == last)
1744		{
1745		// can't repeat any more, remove the pushed state:
1746	16884x	destroy_single_repeat();
1747	16884x	if((m_match_flags & match_partial) && (position == last) && (position != search_base))
1748	792x	m_has_partial_match = true;
1749	16884x	if(0 == (rep->can_be_null & mask_skip))
1750	4356x	return true;
1751		}
1752	20568x	else if(count == rep->max)
1753		{
1754		// can't repeat any more, remove the pushed state:
1755	2148x	destroy_single_repeat();
1756	2148x	if(!can_start(*position, rep->_map, mask_skip))
1757	900x	return true;
1758		}
1759		else
1760		{
1761	18420x	pmp->count = count;
1762	18420x	pmp->last_position = position;
1763		}
1764	32196x	pstate = rep->alt.p;
1765	32196x	return false;
1766		}
1767
1768		template <class BidiIterator, class Allocator, class traits>
1769	20376x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_non_greedy_repeat(bool r)
1770		{
1771	20376x	saved_position<BidiIterator>* pmp = static_cast<saved_position<BidiIterator>*>(m_backup_state);
1772	20376x	if(!r)
1773		{
1774	6456x	position = pmp->position;
1775	6456x	pstate = pmp->pstate;
1776	6456x	++(*next_count);
1777		}
1778	20376x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1779	20376x	m_backup_state = pmp;
1780	20376x	return r;
1781		}
1782
1783		template <class BidiIterator, class Allocator, class traits>
1784	525557x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion(bool r)
1785		{
1786		// We are backtracking back inside a recursion, need to push the info
1787		// back onto the recursion stack, and do so unconditionally, otherwise
1788		// we can get mismatched pushes and pops...
1789	525557x	saved_recursion<results_type>* pmp = static_cast<saved_recursion<results_type>*>(m_backup_state);
1790	525557x	if (!r)
1791		{
1792	435916x	recursion_stack.push_back(recursion_info<results_type>());
1793	435916x	recursion_stack.back().idx = pmp->recursion_id;
1794	435916x	recursion_stack.back().preturn_address = pmp->preturn_address;
1795	435916x	recursion_stack.back().results = pmp->prior_results;
1796	435916x	recursion_stack.back().location_of_start = position;
1797	435916x	*m_presult = pmp->internal_results;
1798		}
1799	525557x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1800	525557x	m_backup_state = pmp;
1801	525557x	return true;
1802		}
1803
1804		template <class BidiIterator, class Allocator, class traits>
1805	510330x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_recursion_pop(bool r)
1806		{
1807		// Backtracking out of a recursion, we must pop state off the recursion
1808		// stack unconditionally to ensure matched pushes and pops:
1809	510330x	saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1810	510330x	if (!r && !recursion_stack.empty())
1811		{
1812	420688x	*m_presult = recursion_stack.back().results;
1813	420688x	position = recursion_stack.back().location_of_start;
1814	420688x	recursion_stack.pop_back();
1815		}
1816	510330x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(pmp++);
1817	510330x	m_backup_state = pmp;
1818	510330x	return true;
1819		}
1820
1821		template <class BidiIterator, class Allocator, class traits>
1822	510330x	void perl_matcher<BidiIterator, Allocator, traits>::push_recursion_pop()
1823		{
1824	510330x	saved_state* pmp = static_cast<saved_state*>(m_backup_state);
1825	510330x	--pmp;
1826	510330x	if(pmp < m_stack_base)
1827		{
1828	411x	extend_stack();
1829	411x	pmp = static_cast<saved_state*>(m_backup_state);
1830	411x	--pmp;
1831		}
1832	510330x	(void) new (pmp)saved_state(15);
1833	510330x	m_backup_state = pmp;
1834	510330x	}
1835
1836		template <class BidiIterator, class Allocator, class traits>
1837	37185x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_commit(bool b)
1838		{
1839	37185x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1840	61020x	while(unwind(b) && !m_unwound_lookahead){}
1841	37185x	if(m_unwound_lookahead && pstate)
1842		{
1843		//
1844		// If we stop because we just unwound an assertion, put the
1845		// commit state back on the stack again:
1846		//
1847	12916x	m_unwound_lookahead = false;
1848	12916x	saved_state* pmp = m_backup_state;
1849	12916x	--pmp;
1850	12916x	if(pmp < m_stack_base)
1851		{
1852	411x	extend_stack();
1853	411x	pmp = m_backup_state;
1854	411x	--pmp;
1855		}
1856	12916x	(void) new (pmp)saved_state(16);
1857	12916x	m_backup_state = pmp;
1858		}
1859		// This prevents us from stopping when we exit from an independent sub-expression:
1860	37185x	m_independent = false;
1861	37185x	return false;
1862		}
1863
1864		template <class BidiIterator, class Allocator, class traits>
1865	8064x	bool perl_matcher<BidiIterator, Allocator, traits>::unwind_then(bool b)
1866		{
1867		// Unwind everything till we hit an alternative:
1868	8064x	boost::BOOST_REGEX_DETAIL_NS::inplace_destroy(m_backup_state++);
1869	8064x	bool result = false;
1870	8064x	result = unwind(b);
1871	9456x	while(result && !m_unwound_alt)
1872		{
1873	1392x	result = unwind(b);
1874		}
1875		// We're now pointing at the next alternative, need one more backtrack
1876		// since all the other alternatives must fail once we've reached a THEN clause:
1877	8064x	if(result && m_unwound_alt)
1878	2880x	unwind(b);
1879	8064x	return false;
1880		}
1881
1882		} // namespace BOOST_REGEX_DETAIL_NS
1883		} // namespace boost
1884
1885		#ifdef BOOST_REGEX_MSVC
1886		# pragma warning(pop)
1887		#endif
1888
1889		#endif
1890