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