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

source code of boost/boost/regex/v4/perl_matcher_non_recursive.hpp