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 * common to both the recursive and non-recursive versions.
18 */
19
20#ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
21#define BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
22
23#ifdef BOOST_MSVC
24#pragma warning(push)
25#pragma warning(disable: 4103)
26#endif
27#ifdef BOOST_HAS_ABI_HEADERS
28# include BOOST_ABI_PREFIX
29#endif
30#ifdef BOOST_MSVC
31#pragma warning(pop)
32#endif
33
34#ifdef __BORLANDC__
35# pragma option push -w-8008 -w-8066
36#endif
37#ifdef BOOST_MSVC
38# pragma warning(push)
39#if BOOST_MSVC < 1910
40#pragma warning(disable:4800)
41#endif
42#endif
43
44namespace boost{
45namespace BOOST_REGEX_DETAIL_NS{
46
47template <class BidiIterator, class Allocator, class traits>
48void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)
49{
50 typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;
51 typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;
52
53 if(e.empty())
54 {
55 // precondition failure: e is not a valid regex.
56 std::invalid_argument ex("Invalid regular expression object");
57 boost::throw_exception(ex);
58 }
59 pstate = 0;
60 m_match_flags = f;
61 estimate_max_state_count(static_cast<category*>(0));
62 expression_flag_type re_f = re.flags();
63 icase = re_f & regex_constants::icase;
64 if(!(m_match_flags & (match_perl|match_posix)))
65 {
66 if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
67 m_match_flags |= match_perl;
68 else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
69 m_match_flags |= match_perl;
70 else if((re_f & (regbase::main_option_type|regbase::literal)) == (regbase::literal))
71 m_match_flags |= match_perl;
72 else
73 m_match_flags |= match_posix;
74 }
75 if(m_match_flags & match_posix)
76 {
77 m_temp_match.reset(new match_results<BidiIterator, Allocator>());
78 m_presult = m_temp_match.get();
79 }
80 else
81 m_presult = &m_result;
82#ifdef BOOST_REGEX_NON_RECURSIVE
83 m_stack_base = 0;
84 m_backup_state = 0;
85#elif defined(BOOST_REGEX_RECURSIVE)
86 m_can_backtrack = true;
87 m_have_accept = false;
88#endif
89 // find the value to use for matching word boundaries:
90 m_word_mask = re.get_data().m_word_mask;
91 // find bitmask to use for matching '.':
92 match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? BOOST_REGEX_DETAIL_NS::test_not_newline : BOOST_REGEX_DETAIL_NS::test_newline);
93 // Disable match_any if requested in the state machine:
94 if(e.get_data().m_disable_match_any)
95 m_match_flags &= regex_constants::match_not_any;
96}
97
98template <class BidiIterator, class Allocator, class traits>
99void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)
100{
101 //
102 // How many states should we allow our machine to visit before giving up?
103 // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)
104 // where N is the length of the string, and S is the number of states
105 // in the machine. It's tempting to up this to O(N^2S) or even O(N^2S^2)
106 // but these take unreasonably amounts of time to bale out in pathological
107 // cases.
108 //
109 // Calculate NS^2 first:
110 //
111 static const std::ptrdiff_t k = 100000;
112 std::ptrdiff_t dist = boost::BOOST_REGEX_DETAIL_NS::distance(base, last);
113 if(dist == 0)
114 dist = 1;
115 std::ptrdiff_t states = re.size();
116 if(states == 0)
117 states = 1;
118 if ((std::numeric_limits<std::ptrdiff_t>::max)() / states < states)
119 {
120 max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
121 return;
122 }
123 states *= states;
124 if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
125 {
126 max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
127 return;
128 }
129 states *= dist;
130 if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
131 {
132 max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
133 return;
134 }
135 states += k;
136
137 max_state_count = states;
138
139 //
140 // Now calculate N^2:
141 //
142 states = dist;
143 if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
144 {
145 max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
146 return;
147 }
148 states *= dist;
149 if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
150 {
151 max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
152 return;
153 }
154 states += k;
155 //
156 // N^2 can be a very large number indeed, to prevent things getting out
157 // of control, cap the max states:
158 //
159 if(states > BOOST_REGEX_MAX_STATE_COUNT)
160 states = BOOST_REGEX_MAX_STATE_COUNT;
161 //
162 // If (the possibly capped) N^2 is larger than our first estimate,
163 // use this instead:
164 //
165 if(states > max_state_count)
166 max_state_count = states;
167}
168
169template <class BidiIterator, class Allocator, class traits>
170inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
171{
172 // we don't know how long the sequence is:
173 max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
174}
175
176#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
177template <class BidiIterator, class Allocator, class traits>
178inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
179 protected_proc_type proc)
180{
181 ::boost::BOOST_REGEX_DETAIL_NS::concrete_protected_call
182 <perl_matcher<BidiIterator, Allocator, traits> >
183 obj(this, proc);
184 return obj.execute();
185
186}
187#endif
188
189template <class BidiIterator, class Allocator, class traits>
190inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
191{
192#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
193 return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
194#else
195 return match_imp();
196#endif
197}
198
199template <class BidiIterator, class Allocator, class traits>
200bool perl_matcher<BidiIterator, Allocator, traits>::match_imp()
201{
202 // initialise our stack if we are non-recursive:
203#ifdef BOOST_REGEX_NON_RECURSIVE
204 save_state_init init(&m_stack_base, &m_backup_state);
205 used_block_count = BOOST_REGEX_MAX_BLOCKS;
206#if !defined(BOOST_NO_EXCEPTIONS)
207 try{
208#endif
209#endif
210
211 // reset our state machine:
212 position = base;
213 search_base = base;
214 state_count = 0;
215 m_match_flags |= regex_constants::match_all;
216 m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), search_base, last);
217 m_presult->set_base(base);
218 m_presult->set_named_subs(this->re.get_named_subs());
219 if(m_match_flags & match_posix)
220 m_result = *m_presult;
221 verify_options(re.flags(), m_match_flags);
222 if(0 == match_prefix())
223 return false;
224 return (m_result[0].second == last) && (m_result[0].first == base);
225
226#if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
227 }
228 catch(...)
229 {
230 // unwind all pushed states, apart from anything else this
231 // ensures that all the states are correctly destructed
232 // not just the memory freed.
233 while(unwind(true)){}
234 throw;
235 }
236#endif
237}
238
239template <class BidiIterator, class Allocator, class traits>
240inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
241{
242#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
243 return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
244#else
245 return find_imp();
246#endif
247}
248
249template <class BidiIterator, class Allocator, class traits>
250bool perl_matcher<BidiIterator, Allocator, traits>::find_imp()
251{
252 static matcher_proc_type const s_find_vtable[7] =
253 {
254 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_any,
255 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_word,
256 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_line,
257 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf,
258 &perl_matcher<BidiIterator, Allocator, traits>::match_prefix,
259 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
260 &perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit,
261 };
262
263 // initialise our stack if we are non-recursive:
264#ifdef BOOST_REGEX_NON_RECURSIVE
265 save_state_init init(&m_stack_base, &m_backup_state);
266 used_block_count = BOOST_REGEX_MAX_BLOCKS;
267#if !defined(BOOST_NO_EXCEPTIONS)
268 try{
269#endif
270#endif
271
272 state_count = 0;
273 if((m_match_flags & regex_constants::match_init) == 0)
274 {
275 // reset our state machine:
276 search_base = position = base;
277 pstate = re.get_first_state();
278 m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), base, last);
279 m_presult->set_base(base);
280 m_presult->set_named_subs(this->re.get_named_subs());
281 m_match_flags |= regex_constants::match_init;
282 }
283 else
284 {
285 // start again:
286 search_base = position = m_result[0].second;
287 // If last match was null and match_not_null was not set then increment
288 // our start position, otherwise we go into an infinite loop:
289 if(((m_match_flags & match_not_null) == 0) && (m_result.length() == 0))
290 {
291 if(position == last)
292 return false;
293 else
294 ++position;
295 }
296 // reset $` start:
297 m_presult->set_size((m_match_flags & match_nosubs) ? 1u : static_cast<typename results_type::size_type>(1u + re.mark_count()), search_base, last);
298 //if((base != search_base) && (base == backstop))
299 // m_match_flags |= match_prev_avail;
300 }
301 if(m_match_flags & match_posix)
302 {
303 m_result.set_size(static_cast<typename results_type::size_type>(1u + re.mark_count()), base, last);
304 m_result.set_base(base);
305 }
306
307 verify_options(re.flags(), m_match_flags);
308 // find out what kind of expression we have:
309 unsigned type = (m_match_flags & match_continuous) ?
310 static_cast<unsigned int>(regbase::restart_continue)
311 : static_cast<unsigned int>(re.get_restart_type());
312
313 // call the appropriate search routine:
314 matcher_proc_type proc = s_find_vtable[type];
315 return (this->*proc)();
316
317#if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
318 }
319 catch(...)
320 {
321 // unwind all pushed states, apart from anything else this
322 // ensures that all the states are correctly destructed
323 // not just the memory freed.
324 while(unwind(true)){}
325 throw;
326 }
327#endif
328}
329
330template <class BidiIterator, class Allocator, class traits>
331bool perl_matcher<BidiIterator, Allocator, traits>::match_prefix()
332{
333 m_has_partial_match = false;
334 m_has_found_match = false;
335 pstate = re.get_first_state();
336 m_presult->set_first(position);
337 restart = position;
338 match_all_states();
339 if(!m_has_found_match && m_has_partial_match && (m_match_flags & match_partial))
340 {
341 m_has_found_match = true;
342 m_presult->set_second(last, 0, false);
343 position = last;
344 if((m_match_flags & match_posix) == match_posix)
345 {
346 m_result.maybe_assign(*m_presult);
347 }
348 }
349#ifdef BOOST_REGEX_MATCH_EXTRA
350 if(m_has_found_match && (match_extra & m_match_flags))
351 {
352 //
353 // we have a match, reverse the capture information:
354 //
355 for(unsigned i = 0; i < m_presult->size(); ++i)
356 {
357 typename sub_match<BidiIterator>::capture_sequence_type & seq = ((*m_presult)[i]).get_captures();
358 std::reverse(seq.begin(), seq.end());
359 }
360 }
361#endif
362 if(!m_has_found_match)
363 position = restart; // reset search postion
364#ifdef BOOST_REGEX_RECURSIVE
365 m_can_backtrack = true; // reset for further searches
366#endif
367 return m_has_found_match;
368}
369
370template <class BidiIterator, class Allocator, class traits>
371bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
372{
373 unsigned int len = static_cast<const re_literal*>(pstate)->length;
374 const char_type* what = reinterpret_cast<const char_type*>(static_cast<const re_literal*>(pstate) + 1);
375 //
376 // compare string with what we stored in
377 // our records:
378 for(unsigned int i = 0; i < len; ++i, ++position)
379 {
380 if((position == last) || (traits_inst.translate(*position, icase) != what[i]))
381 return false;
382 }
383 pstate = pstate->next.p;
384 return true;
385}
386
387template <class BidiIterator, class Allocator, class traits>
388bool perl_matcher<BidiIterator, Allocator, traits>::match_start_line()
389{
390 if(position == backstop)
391 {
392 if((m_match_flags & match_prev_avail) == 0)
393 {
394 if((m_match_flags & match_not_bol) == 0)
395 {
396 pstate = pstate->next.p;
397 return true;
398 }
399 return false;
400 }
401 }
402 else if(m_match_flags & match_single_line)
403 return false;
404
405 // check the previous value character:
406 BidiIterator t(position);
407 --t;
408 if(position != last)
409 {
410 if(is_separator(*t) && !((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n'))) )
411 {
412 pstate = pstate->next.p;
413 return true;
414 }
415 }
416 else if(is_separator(*t))
417 {
418 pstate = pstate->next.p;
419 return true;
420 }
421 return false;
422}
423
424template <class BidiIterator, class Allocator, class traits>
425bool perl_matcher<BidiIterator, Allocator, traits>::match_end_line()
426{
427 if(position != last)
428 {
429 if(m_match_flags & match_single_line)
430 return false;
431 // we're not yet at the end so *first is always valid:
432 if(is_separator(*position))
433 {
434 if((position != backstop) || (m_match_flags & match_prev_avail))
435 {
436 // check that we're not in the middle of \r\n sequence
437 BidiIterator t(position);
438 --t;
439 if((*t == static_cast<char_type>('\r')) && (*position == static_cast<char_type>('\n')))
440 {
441 return false;
442 }
443 }
444 pstate = pstate->next.p;
445 return true;
446 }
447 }
448 else if((m_match_flags & match_not_eol) == 0)
449 {
450 pstate = pstate->next.p;
451 return true;
452 }
453 return false;
454}
455
456template <class BidiIterator, class Allocator, class traits>
457bool perl_matcher<BidiIterator, Allocator, traits>::match_wild()
458{
459 if(position == last)
460 return false;
461 if(is_separator(*position) && ((match_any_mask & static_cast<const re_dot*>(pstate)->mask) == 0))
462 return false;
463 if((*position == char_type(0)) && (m_match_flags & match_not_dot_null))
464 return false;
465 pstate = pstate->next.p;
466 ++position;
467 return true;
468}
469
470template <class BidiIterator, class Allocator, class traits>
471bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
472{
473 bool b; // indcates whether next character is a word character
474 if(position != last)
475 {
476 // prev and this character must be opposites:
477 b = traits_inst.isctype(*position, m_word_mask);
478 }
479 else
480 {
481 if (m_match_flags & match_not_eow)
482 return false;
483 b = false;
484 }
485 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
486 {
487 if(m_match_flags & match_not_bow)
488 return false;
489 else
490 b ^= false;
491 }
492 else
493 {
494 --position;
495 b ^= traits_inst.isctype(*position, m_word_mask);
496 ++position;
497 }
498 if(b)
499 {
500 pstate = pstate->next.p;
501 return true;
502 }
503 return false; // no match if we get to here...
504}
505
506template <class BidiIterator, class Allocator, class traits>
507bool perl_matcher<BidiIterator, Allocator, traits>::match_within_word()
508{
509 if(position == last)
510 return false;
511 // both prev and this character must be m_word_mask:
512 bool prev = traits_inst.isctype(*position, m_word_mask);
513 {
514 bool b;
515 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
516 return false;
517 else
518 {
519 --position;
520 b = traits_inst.isctype(*position, m_word_mask);
521 ++position;
522 }
523 if(b == prev)
524 {
525 pstate = pstate->next.p;
526 return true;
527 }
528 }
529 return false;
530}
531
532template <class BidiIterator, class Allocator, class traits>
533bool perl_matcher<BidiIterator, Allocator, traits>::match_word_start()
534{
535 if(position == last)
536 return false; // can't be starting a word if we're already at the end of input
537 if(!traits_inst.isctype(*position, m_word_mask))
538 return false; // next character isn't a word character
539 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
540 {
541 if(m_match_flags & match_not_bow)
542 return false; // no previous input
543 }
544 else
545 {
546 // otherwise inside buffer:
547 BidiIterator t(position);
548 --t;
549 if(traits_inst.isctype(*t, m_word_mask))
550 return false; // previous character not non-word
551 }
552 // OK we have a match:
553 pstate = pstate->next.p;
554 return true;
555}
556
557template <class BidiIterator, class Allocator, class traits>
558bool perl_matcher<BidiIterator, Allocator, traits>::match_word_end()
559{
560 if((position == backstop) && ((m_match_flags & match_prev_avail) == 0))
561 return false; // start of buffer can't be end of word
562 BidiIterator t(position);
563 --t;
564 if(traits_inst.isctype(*t, m_word_mask) == false)
565 return false; // previous character wasn't a word character
566
567 if(position == last)
568 {
569 if(m_match_flags & match_not_eow)
570 return false; // end of buffer but not end of word
571 }
572 else
573 {
574 // otherwise inside buffer:
575 if(traits_inst.isctype(*position, m_word_mask))
576 return false; // next character is a word character
577 }
578 pstate = pstate->next.p;
579 return true; // if we fall through to here then we've succeeded
580}
581
582template <class BidiIterator, class Allocator, class traits>
583bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start()
584{
585 if((position != backstop) || (m_match_flags & match_not_bob))
586 return false;
587 // OK match:
588 pstate = pstate->next.p;
589 return true;
590}
591
592template <class BidiIterator, class Allocator, class traits>
593bool perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end()
594{
595 if((position != last) || (m_match_flags & match_not_eob))
596 return false;
597 // OK match:
598 pstate = pstate->next.p;
599 return true;
600}
601
602template <class BidiIterator, class Allocator, class traits>
603bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
604{
605 //
606 // Compare with what we previously matched.
607 // Note that this succeeds if the backref did not partisipate
608 // in the match, this is in line with ECMAScript, but not Perl
609 // or PCRE.
610 //
611 int index = static_cast<const re_brace*>(pstate)->index;
612 if(index >= 10000)
613 {
614 named_subexpressions::range_type r = re.get_data().equal_range(index);
615 BOOST_ASSERT(r.first != r.second);
616 do
617 {
618 index = r.first->index;
619 ++r.first;
620 }while((r.first != r.second) && ((*m_presult)[index].matched != true));
621 }
622
623 if((m_match_flags & match_perl) && !(*m_presult)[index].matched)
624 return false;
625
626 BidiIterator i = (*m_presult)[index].first;
627 BidiIterator j = (*m_presult)[index].second;
628 while(i != j)
629 {
630 if((position == last) || (traits_inst.translate(*position, icase) != traits_inst.translate(*i, icase)))
631 return false;
632 ++i;
633 ++position;
634 }
635 pstate = pstate->next.p;
636 return true;
637}
638
639template <class BidiIterator, class Allocator, class traits>
640bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set()
641{
642 typedef typename traits::char_class_type char_class_type;
643 // let the traits class do the work:
644 if(position == last)
645 return false;
646 BidiIterator t = re_is_set_member(position, last, static_cast<const re_set_long<char_class_type>*>(pstate), re.get_data(), icase);
647 if(t != position)
648 {
649 pstate = pstate->next.p;
650 position = t;
651 return true;
652 }
653 return false;
654}
655
656template <class BidiIterator, class Allocator, class traits>
657bool perl_matcher<BidiIterator, Allocator, traits>::match_set()
658{
659 if(position == last)
660 return false;
661 if(static_cast<const re_set*>(pstate)->_map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
662 {
663 pstate = pstate->next.p;
664 ++position;
665 return true;
666 }
667 return false;
668}
669
670template <class BidiIterator, class Allocator, class traits>
671bool perl_matcher<BidiIterator, Allocator, traits>::match_jump()
672{
673 pstate = static_cast<const re_jump*>(pstate)->alt.p;
674 return true;
675}
676
677template <class BidiIterator, class Allocator, class traits>
678bool perl_matcher<BidiIterator, Allocator, traits>::match_combining()
679{
680 if(position == last)
681 return false;
682 if(is_combining(traits_inst.translate(*position, icase)))
683 return false;
684 ++position;
685 while((position != last) && is_combining(traits_inst.translate(*position, icase)))
686 ++position;
687 pstate = pstate->next.p;
688 return true;
689}
690
691template <class BidiIterator, class Allocator, class traits>
692bool perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end()
693{
694 if(m_match_flags & match_not_eob)
695 return false;
696 BidiIterator p(position);
697 while((p != last) && is_separator(traits_inst.translate(*p, icase)))++p;
698 if(p != last)
699 return false;
700 pstate = pstate->next.p;
701 return true;
702}
703
704template <class BidiIterator, class Allocator, class traits>
705bool perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue()
706{
707 if(position == search_base)
708 {
709 pstate = pstate->next.p;
710 return true;
711 }
712 return false;
713}
714
715template <class BidiIterator, class Allocator, class traits>
716bool perl_matcher<BidiIterator, Allocator, traits>::match_backstep()
717{
718#ifdef BOOST_MSVC
719#pragma warning(push)
720#pragma warning(disable:4127)
721#endif
722 if( ::boost::is_random_access_iterator<BidiIterator>::value)
723 {
724 std::ptrdiff_t maxlen = ::boost::BOOST_REGEX_DETAIL_NS::distance(backstop, position);
725 if(maxlen < static_cast<const re_brace*>(pstate)->index)
726 return false;
727 std::advance(position, -static_cast<const re_brace*>(pstate)->index);
728 }
729 else
730 {
731 int c = static_cast<const re_brace*>(pstate)->index;
732 while(c--)
733 {
734 if(position == backstop)
735 return false;
736 --position;
737 }
738 }
739 pstate = pstate->next.p;
740 return true;
741#ifdef BOOST_MSVC
742#pragma warning(pop)
743#endif
744}
745
746template <class BidiIterator, class Allocator, class traits>
747inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
748{
749 // return true if marked sub-expression N has been matched:
750 int index = static_cast<const re_brace*>(pstate)->index;
751 bool result = false;
752 if(index == 9999)
753 {
754 // Magic value for a (DEFINE) block:
755 return false;
756 }
757 else if(index > 0)
758 {
759 // Have we matched subexpression "index"?
760 // Check if index is a hash value:
761 if(index >= 10000)
762 {
763 named_subexpressions::range_type r = re.get_data().equal_range(index);
764 while(r.first != r.second)
765 {
766 if((*m_presult)[r.first->index].matched)
767 {
768 result = true;
769 break;
770 }
771 ++r.first;
772 }
773 }
774 else
775 {
776 result = (*m_presult)[index].matched;
777 }
778 pstate = pstate->next.p;
779 }
780 else
781 {
782 // Have we recursed into subexpression "index"?
783 // If index == 0 then check for any recursion at all, otherwise for recursion to -index-1.
784 int idx = -(index+1);
785 if(idx >= 10000)
786 {
787 named_subexpressions::range_type r = re.get_data().equal_range(idx);
788 int stack_index = recursion_stack.empty() ? -1 : recursion_stack.back().idx;
789 while(r.first != r.second)
790 {
791 result |= (stack_index == r.first->index);
792 if(result)break;
793 ++r.first;
794 }
795 }
796 else
797 {
798 result = !recursion_stack.empty() && ((recursion_stack.back().idx == idx) || (index == 0));
799 }
800 pstate = pstate->next.p;
801 }
802 return result;
803}
804
805template <class BidiIterator, class Allocator, class traits>
806bool perl_matcher<BidiIterator, Allocator, traits>::match_fail()
807{
808 // Just force a backtrack:
809 return false;
810}
811
812template <class BidiIterator, class Allocator, class traits>
813bool perl_matcher<BidiIterator, Allocator, traits>::match_accept()
814{
815 if(!recursion_stack.empty())
816 {
817 return skip_until_paren(recursion_stack.back().idx);
818 }
819 else
820 {
821 return skip_until_paren(INT_MAX);
822 }
823}
824
825template <class BidiIterator, class Allocator, class traits>
826bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_any()
827{
828#ifdef BOOST_MSVC
829#pragma warning(push)
830#pragma warning(disable:4127)
831#endif
832 const unsigned char* _map = re.get_map();
833 while(true)
834 {
835 // skip everything we can't match:
836 while((position != last) && !can_start(*position, _map, (unsigned char)mask_any) )
837 ++position;
838 if(position == last)
839 {
840 // run out of characters, try a null match if possible:
841 if(re.can_be_null())
842 return match_prefix();
843 break;
844 }
845 // now try and obtain a match:
846 if(match_prefix())
847 return true;
848 if(position == last)
849 return false;
850 ++position;
851 }
852 return false;
853#ifdef BOOST_MSVC
854#pragma warning(pop)
855#endif
856}
857
858template <class BidiIterator, class Allocator, class traits>
859bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_word()
860{
861#ifdef BOOST_MSVC
862#pragma warning(push)
863#pragma warning(disable:4127)
864#endif
865 // do search optimised for word starts:
866 const unsigned char* _map = re.get_map();
867 if((m_match_flags & match_prev_avail) || (position != base))
868 --position;
869 else if(match_prefix())
870 return true;
871 do
872 {
873 while((position != last) && traits_inst.isctype(*position, m_word_mask))
874 ++position;
875 while((position != last) && !traits_inst.isctype(*position, m_word_mask))
876 ++position;
877 if(position == last)
878 break;
879
880 if(can_start(*position, _map, (unsigned char)mask_any) )
881 {
882 if(match_prefix())
883 return true;
884 }
885 if(position == last)
886 break;
887 } while(true);
888 return false;
889#ifdef BOOST_MSVC
890#pragma warning(pop)
891#endif
892}
893
894template <class BidiIterator, class Allocator, class traits>
895bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_line()
896{
897 // do search optimised for line starts:
898 const unsigned char* _map = re.get_map();
899 if(match_prefix())
900 return true;
901 while(position != last)
902 {
903 while((position != last) && !is_separator(*position))
904 ++position;
905 if(position == last)
906 return false;
907 ++position;
908 if(position == last)
909 {
910 if(re.can_be_null() && match_prefix())
911 return true;
912 return false;
913 }
914
915 if( can_start(*position, _map, (unsigned char)mask_any) )
916 {
917 if(match_prefix())
918 return true;
919 }
920 if(position == last)
921 return false;
922 //++position;
923 }
924 return false;
925}
926
927template <class BidiIterator, class Allocator, class traits>
928bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_buf()
929{
930 if((position == base) && ((m_match_flags & match_not_bob) == 0))
931 return match_prefix();
932 return false;
933}
934
935template <class BidiIterator, class Allocator, class traits>
936bool perl_matcher<BidiIterator, Allocator, traits>::find_restart_lit()
937{
938#if 0
939 if(position == last)
940 return false; // can't possibly match if we're at the end already
941
942 unsigned type = (m_match_flags & match_continuous) ?
943 static_cast<unsigned int>(regbase::restart_continue)
944 : static_cast<unsigned int>(re.get_restart_type());
945
946 const kmp_info<char_type>* info = access::get_kmp(re);
947 int len = info->len;
948 const char_type* x = info->pstr;
949 int j = 0;
950 while (position != last)
951 {
952 while((j > -1) && (x[j] != traits_inst.translate(*position, icase)))
953 j = info->kmp_next[j];
954 ++position;
955 ++j;
956 if(j >= len)
957 {
958 if(type == regbase::restart_fixed_lit)
959 {
960 std::advance(position, -j);
961 restart = position;
962 std::advance(restart, len);
963 m_result.set_first(position);
964 m_result.set_second(restart);
965 position = restart;
966 return true;
967 }
968 else
969 {
970 restart = position;
971 std::advance(position, -j);
972 if(match_prefix())
973 return true;
974 else
975 {
976 for(int k = 0; (restart != position) && (k < j); ++k, --restart)
977 {} // dwa 10/20/2000 - warning suppression for MWCW
978 if(restart != last)
979 ++restart;
980 position = restart;
981 j = 0; //we could do better than this...
982 }
983 }
984 }
985 }
986 if((m_match_flags & match_partial) && (position == last) && j)
987 {
988 // we need to check for a partial match:
989 restart = position;
990 std::advance(position, -j);
991 return match_prefix();
992 }
993#endif
994 return false;
995}
996
997} // namespace BOOST_REGEX_DETAIL_NS
998
999} // namespace boost
1000
1001#ifdef BOOST_MSVC
1002# pragma warning(pop)
1003#endif
1004
1005#ifdef __BORLANDC__
1006# pragma option pop
1007#endif
1008#ifdef BOOST_MSVC
1009#pragma warning(push)
1010#pragma warning(disable: 4103)
1011#endif
1012#ifdef BOOST_HAS_ABI_HEADERS
1013# include BOOST_ABI_SUFFIX
1014#endif
1015#ifdef BOOST_MSVC
1016#pragma warning(pop)
1017#endif
1018
1019#endif
1020
1021