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