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