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> |
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(e: 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_any; |
94 | } |
95 | |
96 | template <class BidiIterator, class Allocator, class traits> |
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 | states *= states; |
117 | if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states) |
118 | { |
119 | max_state_count = (std::min)(a: (std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, b: (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)(a: (std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, b: (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)(a: (std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, b: (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)(a: (std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, b: (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 | |
162 | template <class BidiIterator, class Allocator, class traits> |
163 | inline 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 |
170 | template <class BidiIterator, class Allocator, class traits> |
171 | inline 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 | |
182 | template <class BidiIterator, class Allocator, class traits> |
183 | inline 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 | |
192 | template <class BidiIterator, class Allocator, class traits> |
193 | bool 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) ? 1 : 1 + 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(have_match: true)){} |
227 | throw; |
228 | } |
229 | #endif |
230 | } |
231 | |
232 | template <class BidiIterator, class Allocator, class traits> |
233 | inline 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 | |
242 | template <class BidiIterator, class Allocator, class traits> |
243 | bool 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) ? 1 : 1 + 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) ? 1 : 1 + 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(1 + 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(have_match: true)){} |
318 | throw; |
319 | } |
320 | #endif |
321 | } |
322 | |
323 | template <class BidiIterator, class Allocator, class traits> |
324 | bool 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 | |
363 | template <class BidiIterator, class Allocator, class traits> |
364 | bool 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 | |
380 | template <class BidiIterator, class Allocator, class traits> |
381 | bool 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 | |
417 | template <class BidiIterator, class Allocator, class traits> |
418 | bool 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 | |
449 | template <class BidiIterator, class Allocator, class traits> |
450 | bool 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 | |
463 | template <class BidiIterator, class Allocator, class traits> |
464 | bool 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 | |
497 | template <class BidiIterator, class Allocator, class traits> |
498 | bool 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 | |
523 | template <class BidiIterator, class Allocator, class traits> |
524 | bool 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 | |
548 | template <class BidiIterator, class Allocator, class traits> |
549 | bool 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 | |
573 | template <class BidiIterator, class Allocator, class traits> |
574 | bool 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 | |
583 | template <class BidiIterator, class Allocator, class traits> |
584 | bool 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 | |
593 | template <class BidiIterator, class Allocator, class traits> |
594 | bool 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 | |
630 | template <class BidiIterator, class Allocator, class traits> |
631 | bool 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 | |
647 | template <class BidiIterator, class Allocator, class traits> |
648 | bool 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 | |
661 | template <class BidiIterator, class Allocator, class traits> |
662 | bool perl_matcher<BidiIterator, Allocator, traits>::match_jump() |
663 | { |
664 | pstate = static_cast<const re_jump*>(pstate)->alt.p; |
665 | return true; |
666 | } |
667 | |
668 | template <class BidiIterator, class Allocator, class traits> |
669 | bool 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 | |
682 | template <class BidiIterator, class Allocator, class traits> |
683 | bool 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 | |
695 | template <class BidiIterator, class Allocator, class traits> |
696 | bool 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 | |
706 | template <class BidiIterator, class Allocator, class traits> |
707 | bool 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 | |
737 | template <class BidiIterator, class Allocator, class traits> |
738 | inline 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 | |
796 | template <class BidiIterator, class Allocator, class traits> |
797 | bool perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case() |
798 | { |
799 | // change our case sensitivity: |
800 | this->icase = static_cast<const re_case*>(pstate)->icase; |
801 | pstate = pstate->next.p; |
802 | return true; |
803 | } |
804 | |
805 | template <class BidiIterator, class Allocator, class traits> |
806 | bool perl_matcher<BidiIterator, Allocator, traits>::match_fail() |
807 | { |
808 | // Just force a backtrack: |
809 | return false; |
810 | } |
811 | |
812 | template <class BidiIterator, class Allocator, class traits> |
813 | bool perl_matcher<BidiIterator, Allocator, traits>::match_accept() |
814 | { |
815 | if(!recursion_stack.empty()) |
816 | { |
817 | return skip_until_paren(index: recursion_stack.back().idx); |
818 | } |
819 | else |
820 | { |
821 | return skip_until_paren(INT_MAX); |
822 | } |
823 | } |
824 | |
825 | template <class BidiIterator, class Allocator, class traits> |
826 | bool 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 | |
858 | template <class BidiIterator, class Allocator, class traits> |
859 | bool 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 | |
894 | template <class BidiIterator, class Allocator, class traits> |
895 | bool 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 | |
927 | template <class BidiIterator, class Allocator, class traits> |
928 | bool 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 | |
935 | template <class BidiIterator, class Allocator, class traits> |
936 | bool 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 | |