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