1 /*
2  *
3  * Copyright (c) 2002
4  * John Maddock
5  *
6  * Use, modification and distribution are subject to the
7  * Boost Software License, Version 1.0. (See accompanying file
8  * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
9  *
10  */
11 
12  /*
13   *   LOCATION:    see http://www.boost.org for most recent version.
14   *   FILE         perl_matcher_common.cpp
15   *   VERSION      see <boost/version.hpp>
16   *   DESCRIPTION: Definitions of perl_matcher member functions that are
17   *                specific to the recursive implementation.
18   */
19 
20 #ifndef BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_HPP
21 #define BOOST_REGEX_V4_PERL_MATCHER_RECURSIVE_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 BOOST_MSVC
35 #pragma warning(push)
36 #pragma warning(disable: 4800)
37 #endif
38 
39 namespace boost{
40 namespace re_detail{
41 
42 template <class BidiIterator>
43 class backup_subex
44 {
45    int index;
46    sub_match<BidiIterator> sub;
47 public:
48    template <class A>
backup_subex(const match_results<BidiIterator,A> & w,int i)49    backup_subex(const match_results<BidiIterator, A>& w, int i)
50       : index(i), sub(w[i], false) {}
51    template <class A>
restore(match_results<BidiIterator,A> & w)52    void restore(match_results<BidiIterator, A>& w)
53    {
54       w.set_first(sub.first, index, index == 0);
55       w.set_second(sub.second, index, sub.matched, index == 0);
56    }
get()57    const sub_match<BidiIterator>& get() { return sub; }
58 };
59 
60 template <class BidiIterator, class Allocator, class traits>
match_all_states()61 bool perl_matcher<BidiIterator, Allocator, traits>::match_all_states()
62 {
63    static matcher_proc_type const s_match_vtable[30] =
64    {
65       (&perl_matcher<BidiIterator, Allocator, traits>::match_startmark),
66       &perl_matcher<BidiIterator, Allocator, traits>::match_endmark,
67       &perl_matcher<BidiIterator, Allocator, traits>::match_literal,
68       &perl_matcher<BidiIterator, Allocator, traits>::match_start_line,
69       &perl_matcher<BidiIterator, Allocator, traits>::match_end_line,
70       &perl_matcher<BidiIterator, Allocator, traits>::match_wild,
71       &perl_matcher<BidiIterator, Allocator, traits>::match_match,
72       &perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary,
73       &perl_matcher<BidiIterator, Allocator, traits>::match_within_word,
74       &perl_matcher<BidiIterator, Allocator, traits>::match_word_start,
75       &perl_matcher<BidiIterator, Allocator, traits>::match_word_end,
76       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_start,
77       &perl_matcher<BidiIterator, Allocator, traits>::match_buffer_end,
78       &perl_matcher<BidiIterator, Allocator, traits>::match_backref,
79       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set,
80       &perl_matcher<BidiIterator, Allocator, traits>::match_set,
81       &perl_matcher<BidiIterator, Allocator, traits>::match_jump,
82       &perl_matcher<BidiIterator, Allocator, traits>::match_alt,
83       &perl_matcher<BidiIterator, Allocator, traits>::match_rep,
84       &perl_matcher<BidiIterator, Allocator, traits>::match_combining,
85       &perl_matcher<BidiIterator, Allocator, traits>::match_soft_buffer_end,
86       &perl_matcher<BidiIterator, Allocator, traits>::match_restart_continue,
87       // Although this next line *should* be evaluated at compile time, in practice
88       // some compilers (VC++) emit run-time initialisation which breaks thread
89       // safety, so use a dispatch function instead:
90       //(::boost::is_random_access_iterator<BidiIterator>::value ? &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast : &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow),
91       &perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_dispatch,
92       &perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat,
93       &perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat,
94       &perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat,
95       &perl_matcher<BidiIterator, Allocator, traits>::match_backstep,
96       &perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref,
97       &perl_matcher<BidiIterator, Allocator, traits>::match_toggle_case,
98       &perl_matcher<BidiIterator, Allocator, traits>::match_recursion,
99    };
100 
101    if(state_count > max_state_count)
102       raise_error(traits_inst, regex_constants::error_complexity);
103    while(pstate)
104    {
105       matcher_proc_type proc = s_match_vtable[pstate->type];
106       ++state_count;
107       if(!(this->*proc)())
108       {
109          if((m_match_flags & match_partial) && (position == last) && (position != search_base))
110             m_has_partial_match = true;
111          return 0;
112       }
113    }
114    return true;
115 }
116 
117 template <class BidiIterator, class Allocator, class traits>
match_startmark()118 bool perl_matcher<BidiIterator, Allocator, traits>::match_startmark()
119 {
120    int index = static_cast<const re_brace*>(pstate)->index;
121    icase = static_cast<const re_brace*>(pstate)->icase;
122    bool r = true;
123    switch(index)
124    {
125    case 0:
126       pstate = pstate->next.p;
127       break;
128    case -1:
129    case -2:
130       {
131          // forward lookahead assert:
132          BidiIterator old_position(position);
133          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
134          pstate = pstate->next.p->next.p;
135          r = match_all_states();
136          pstate = next_pstate;
137          position = old_position;
138          if((r && (index != -1)) || (!r && (index != -2)))
139             r = false;
140          else
141             r = true;
142          break;
143       }
144    case -3:
145       {
146          // independent sub-expression:
147          bool old_independent = m_independent;
148          m_independent = true;
149          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
150          pstate = pstate->next.p->next.p;
151          r = match_all_states();
152          pstate = next_pstate;
153          m_independent = old_independent;
154 #ifdef BOOST_REGEX_MATCH_EXTRA
155          if(r && (m_match_flags & match_extra))
156          {
157             //
158             // our captures have been stored in *m_presult
159             // we need to unpack them, and insert them
160             // back in the right order when we unwind the stack:
161             //
162             unsigned i;
163             match_results<BidiIterator, Allocator> tm(*m_presult);
164             for(i = 0; i < tm.size(); ++i)
165                (*m_presult)[i].get_captures().clear();
166             // match everything else:
167             r = match_all_states();
168             // now place the stored captures back:
169             for(i = 0; i < tm.size(); ++i)
170             {
171                typedef typename sub_match<BidiIterator>::capture_sequence_type seq;
172                seq& s1 = (*m_presult)[i].get_captures();
173                const seq& s2 = tm[i].captures();
174                s1.insert(
175                   s1.end(),
176                   s2.begin(),
177                   s2.end());
178             }
179          }
180 #endif
181          break;
182       }
183    case -4:
184       {
185       // conditional expression:
186       const re_alt* alt = static_cast<const re_alt*>(pstate->next.p);
187       BOOST_ASSERT(alt->type == syntax_element_alt);
188       pstate = alt->next.p;
189       if(pstate->type == syntax_element_assert_backref)
190       {
191          if(!match_assert_backref())
192             pstate = alt->alt.p;
193          break;
194       }
195       else
196       {
197          // zero width assertion, have to match this recursively:
198          BOOST_ASSERT(pstate->type == syntax_element_startmark);
199          bool negated = static_cast<const re_brace*>(pstate)->index == -2;
200          BidiIterator saved_position = position;
201          const re_syntax_base* next_pstate = static_cast<const re_jump*>(pstate->next.p)->alt.p->next.p;
202          pstate = pstate->next.p->next.p;
203          bool res = match_all_states();
204          position = saved_position;
205          if(negated)
206             res = !res;
207          if(res)
208             pstate = next_pstate;
209          else
210             pstate = alt->alt.p;
211          break;
212       }
213       }
214    case -5:
215       {
216          // Reset start of $0, since we have a \K escape
217          backup_subex<BidiIterator> sub(*m_presult, 0);
218          m_presult->set_first(position, 0, true);
219          pstate = pstate->next.p;
220          r = match_all_states();
221          if(r == false)
222             sub.restore(*m_presult);
223          break;
224       }
225    default:
226    {
227       BOOST_ASSERT(index > 0);
228       if((m_match_flags & match_nosubs) == 0)
229       {
230          backup_subex<BidiIterator> sub(*m_presult, index);
231          m_presult->set_first(position, index);
232          pstate = pstate->next.p;
233          r = match_all_states();
234          if(r == false)
235             sub.restore(*m_presult);
236 #ifdef BOOST_REGEX_MATCH_EXTRA
237          //
238          // we have a match, push the capture information onto the stack:
239          //
240          else if(sub.get().matched && (match_extra & m_match_flags))
241             ((*m_presult)[index]).get_captures().push_back(sub.get());
242 #endif
243       }
244       else
245       {
246          pstate = pstate->next.p;
247       }
248       break;
249    }
250    }
251    return r;
252 }
253 
254 template <class BidiIterator, class Allocator, class traits>
match_alt()255 bool perl_matcher<BidiIterator, Allocator, traits>::match_alt()
256 {
257    bool take_first, take_second;
258    const re_alt* jmp = static_cast<const re_alt*>(pstate);
259 
260    // find out which of these two alternatives we need to take:
261    if(position == last)
262    {
263       take_first = jmp->can_be_null & mask_take;
264       take_second = jmp->can_be_null & mask_skip;
265    }
266    else
267    {
268       take_first = can_start(*position, jmp->_map, (unsigned char)mask_take);
269       take_second = can_start(*position, jmp->_map, (unsigned char)mask_skip);
270   }
271 
272    if(take_first)
273    {
274       // we can take the first alternative,
275       // see if we need to push next alternative:
276       if(take_second)
277       {
278          BidiIterator oldposition(position);
279          const re_syntax_base* old_pstate = jmp->alt.p;
280          pstate = pstate->next.p;
281          if(!match_all_states())
282          {
283             pstate = old_pstate;
284             position = oldposition;
285          }
286          return true;
287       }
288       pstate = pstate->next.p;
289       return true;
290    }
291    if(take_second)
292    {
293       pstate = jmp->alt.p;
294       return true;
295    }
296    return false;  // neither option is possible
297 }
298 
299 template <class BidiIterator, class Allocator, class traits>
match_rep()300 bool perl_matcher<BidiIterator, Allocator, traits>::match_rep()
301 {
302 #ifdef BOOST_MSVC
303 #pragma warning(push)
304 #pragma warning(disable:4127 4244)
305 #endif
306    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
307    //
308    // Always copy the repeat count, so that the state is restored
309    // when we exit this scope:
310    //
311    repeater_count<BidiIterator> r(rep->state_id, &next_count, position);
312    //
313    // If we've had at least one repeat already, and the last one
314    // matched the NULL string then set the repeat count to
315    // maximum:
316    //
317    next_count->check_null_repeat(position, rep->max);
318 
319    // find out which of these two alternatives we need to take:
320    bool take_first, take_second;
321    if(position == last)
322    {
323       take_first = rep->can_be_null & mask_take;
324       take_second = rep->can_be_null & mask_skip;
325    }
326    else
327    {
328       take_first = can_start(*position, rep->_map, (unsigned char)mask_take);
329       take_second = can_start(*position, rep->_map, (unsigned char)mask_skip);
330    }
331 
332    if(next_count->get_count() < rep->min)
333    {
334       // we must take the repeat:
335       if(take_first)
336       {
337          // increase the counter:
338          ++(*next_count);
339          pstate = rep->next.p;
340          return match_all_states();
341       }
342       return false;
343    }
344    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
345    if(greedy)
346    {
347       // try and take the repeat if we can:
348       if((next_count->get_count() < rep->max) && take_first)
349       {
350          // store position in case we fail:
351          BidiIterator pos = position;
352          // increase the counter:
353          ++(*next_count);
354          pstate = rep->next.p;
355          if(match_all_states())
356             return true;
357          // failed repeat, reset posistion and fall through for alternative:
358          position = pos;
359       }
360       if(take_second)
361       {
362          pstate = rep->alt.p;
363          return true;
364       }
365       return false; // can't take anything, fail...
366    }
367    else // non-greedy
368    {
369       // try and skip the repeat if we can:
370       if(take_second)
371       {
372          // store position in case we fail:
373          BidiIterator pos = position;
374          pstate = rep->alt.p;
375          if(match_all_states())
376             return true;
377          // failed alternative, reset posistion and fall through for repeat:
378          position = pos;
379       }
380       if((next_count->get_count() < rep->max) && take_first)
381       {
382          // increase the counter:
383          ++(*next_count);
384          pstate = rep->next.p;
385          return match_all_states();
386       }
387    }
388    return false;
389 #ifdef BOOST_MSVC
390 #pragma warning(pop)
391 #endif
392 }
393 
394 template <class BidiIterator, class Allocator, class traits>
match_dot_repeat_slow()395 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_slow()
396 {
397 #ifdef BOOST_MSVC
398 #pragma warning(push)
399 #pragma warning(disable:4127)
400 #endif
401    unsigned count = 0;
402    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
403    re_syntax_base* psingle = rep->next.p;
404    // match compulsary repeats first:
405    while(count < rep->min)
406    {
407       pstate = psingle;
408       if(!match_wild())
409          return false;
410       ++count;
411    }
412    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
413    if(greedy)
414    {
415       // normal repeat:
416       while(count < rep->max)
417       {
418          pstate = psingle;
419          if(!match_wild())
420             break;
421          ++count;
422       }
423       if((rep->leading) && (count < rep->max))
424          restart = position;
425       pstate = rep;
426       return backtrack_till_match(count - rep->min);
427    }
428    else
429    {
430       // non-greedy, keep trying till we get a match:
431       BidiIterator save_pos;
432       do
433       {
434          if((rep->leading) && (rep->max == UINT_MAX))
435             restart = position;
436          pstate = rep->alt.p;
437          save_pos = position;
438          ++state_count;
439          if(match_all_states())
440             return true;
441          if(count >= rep->max)
442             return false;
443          ++count;
444          pstate = psingle;
445          position = save_pos;
446          if(!match_wild())
447             return false;
448       }while(true);
449    }
450 #ifdef BOOST_MSVC
451 #pragma warning(pop)
452 #endif
453 }
454 
455 template <class BidiIterator, class Allocator, class traits>
match_dot_repeat_fast()456 bool perl_matcher<BidiIterator, Allocator, traits>::match_dot_repeat_fast()
457 {
458 #ifdef BOOST_MSVC
459 #pragma warning(push)
460 #pragma warning(disable:4127)
461 #endif
462    if(m_match_flags & match_not_dot_null)
463       return match_dot_repeat_slow();
464    if((static_cast<const re_dot*>(pstate->next.p)->mask & match_any_mask) == 0)
465       return match_dot_repeat_slow();
466    //
467    // start by working out how much we can skip:
468    //
469    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
470 #ifdef BOOST_MSVC
471 #pragma warning(push)
472 #pragma warning(disable:4267)
473 #endif
474    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
475    std::size_t count = (std::min)(static_cast<std::size_t>(::boost::re_detail::distance(position, last)), static_cast<std::size_t>(greedy ? rep->max : rep->min));
476    if(rep->min > count)
477    {
478       position = last;
479       return false;  // not enough text left to match
480    }
481    std::advance(position, count);
482 #ifdef BOOST_MSVC
483 #pragma warning(pop)
484 #endif
485    if((rep->leading) && (count < rep->max) && greedy)
486       restart = position;
487    if(greedy)
488       return backtrack_till_match(count - rep->min);
489 
490    // non-greedy, keep trying till we get a match:
491    BidiIterator save_pos;
492    do
493    {
494       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
495       {
496          ++position;
497          ++count;
498       }
499       if((rep->leading) && (rep->max == UINT_MAX))
500          restart = position;
501       pstate = rep->alt.p;
502       save_pos = position;
503       ++state_count;
504       if(match_all_states())
505          return true;
506       if(count >= rep->max)
507          return false;
508       if(save_pos == last)
509          return false;
510       position = ++save_pos;
511       ++count;
512    }while(true);
513 #ifdef BOOST_MSVC
514 #pragma warning(pop)
515 #endif
516 }
517 
518 template <class BidiIterator, class Allocator, class traits>
match_char_repeat()519 bool perl_matcher<BidiIterator, Allocator, traits>::match_char_repeat()
520 {
521 #ifdef BOOST_MSVC
522 #pragma warning(push)
523 #pragma warning(disable:4127)
524 #pragma warning(disable:4267)
525 #endif
526 #ifdef __BORLANDC__
527 #pragma option push -w-8008 -w-8066 -w-8004
528 #endif
529    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
530    BOOST_ASSERT(1 == static_cast<const re_literal*>(rep->next.p)->length);
531    const char_type what = *reinterpret_cast<const char_type*>(static_cast<const re_literal*>(rep->next.p) + 1);
532    //
533    // start by working out how much we can skip:
534    //
535    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
536    std::size_t count, desired;
537    if(::boost::is_random_access_iterator<BidiIterator>::value)
538    {
539       desired =
540          (std::min)(
541             (std::size_t)(greedy ? rep->max : rep->min),
542             (std::size_t)::boost::re_detail::distance(position, last));
543       count = desired;
544       ++desired;
545       if(icase)
546       {
547          while(--desired && (traits_inst.translate_nocase(*position) == what))
548          {
549             ++position;
550          }
551       }
552       else
553       {
554          while(--desired && (traits_inst.translate(*position) == what))
555          {
556             ++position;
557          }
558       }
559       count = count - desired;
560    }
561    else
562    {
563       count = 0;
564       desired = greedy ? rep->max : rep->min;
565       while((count < desired) && (position != last) && (traits_inst.translate(*position, icase) == what))
566       {
567          ++position;
568          ++count;
569       }
570    }
571    if((rep->leading) && (count < rep->max) && greedy)
572       restart = position;
573    if(count < rep->min)
574       return false;
575 
576    if(greedy)
577       return backtrack_till_match(count - rep->min);
578 
579    // non-greedy, keep trying till we get a match:
580    BidiIterator save_pos;
581    do
582    {
583       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
584       {
585          if((traits_inst.translate(*position, icase) == what))
586          {
587             ++position;
588             ++count;
589          }
590          else
591             return false;  // counldn't repeat even though it was the only option
592       }
593       if((rep->leading) && (rep->max == UINT_MAX))
594          restart = position;
595       pstate = rep->alt.p;
596       save_pos = position;
597       ++state_count;
598       if(match_all_states())
599          return true;
600       if(count >= rep->max)
601          return false;
602       position = save_pos;
603       if(position == last)
604          return false;
605       if(traits_inst.translate(*position, icase) == what)
606       {
607          ++position;
608          ++count;
609       }
610       else
611       {
612          return false;
613       }
614    }while(true);
615 #ifdef __BORLANDC__
616 #pragma option pop
617 #endif
618 #ifdef BOOST_MSVC
619 #pragma warning(pop)
620 #endif
621 }
622 
623 template <class BidiIterator, class Allocator, class traits>
match_set_repeat()624 bool perl_matcher<BidiIterator, Allocator, traits>::match_set_repeat()
625 {
626 #ifdef BOOST_MSVC
627 #pragma warning(push)
628 #pragma warning(disable:4127)
629 #endif
630 #ifdef __BORLANDC__
631 #pragma option push -w-8008 -w-8066 -w-8004
632 #endif
633    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
634    const unsigned char* map = static_cast<const re_set*>(rep->next.p)->_map;
635    unsigned count = 0;
636    //
637    // start by working out how much we can skip:
638    //
639    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
640    std::size_t desired = greedy ? rep->max : rep->min;
641    if(::boost::is_random_access_iterator<BidiIterator>::value)
642    {
643       BidiIterator end = position;
644       // Move end forward by "desired", preferably without using distance or advance if we can
645       // as these can be slow for some iterator types.
646       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::re_detail::distance(position, last);
647       if(desired >= len)
648          end = last;
649       else
650          std::advance(end, desired);
651       BidiIterator origin(position);
652       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
653       {
654          ++position;
655       }
656       count = (unsigned)::boost::re_detail::distance(origin, position);
657    }
658    else
659    {
660       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
661       {
662          ++position;
663          ++count;
664       }
665    }
666    if((rep->leading) && (count < rep->max) && greedy)
667       restart = position;
668    if(count < rep->min)
669       return false;
670 
671    if(greedy)
672       return backtrack_till_match(count - rep->min);
673 
674    // non-greedy, keep trying till we get a match:
675    BidiIterator save_pos;
676    do
677    {
678       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
679       {
680          if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
681          {
682             ++position;
683             ++count;
684          }
685          else
686             return false;  // counldn't repeat even though it was the only option
687       }
688       if((rep->leading) && (rep->max == UINT_MAX))
689          restart = position;
690       pstate = rep->alt.p;
691       save_pos = position;
692       ++state_count;
693       if(match_all_states())
694          return true;
695       if(count >= rep->max)
696          return false;
697       position = save_pos;
698       if(position == last)
699          return false;
700       if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
701       {
702          ++position;
703          ++count;
704       }
705       else
706       {
707          return false;
708       }
709    }while(true);
710 #ifdef __BORLANDC__
711 #pragma option pop
712 #endif
713 #ifdef BOOST_MSVC
714 #pragma warning(pop)
715 #endif
716 }
717 
718 template <class BidiIterator, class Allocator, class traits>
match_long_set_repeat()719 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
720 {
721 #ifdef BOOST_MSVC
722 #pragma warning(push)
723 #pragma warning(disable:4127)
724 #endif
725 #ifdef __BORLANDC__
726 #pragma option push -w-8008 -w-8066 -w-8004
727 #endif
728    typedef typename traits::char_class_type char_class_type;
729    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
730    const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
731    unsigned count = 0;
732    //
733    // start by working out how much we can skip:
734    //
735    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
736    std::size_t desired = greedy ? rep->max : rep->min;
737    if(::boost::is_random_access_iterator<BidiIterator>::value)
738    {
739       BidiIterator end = position;
740       // Move end forward by "desired", preferably without using distance or advance if we can
741       // as these can be slow for some iterator types.
742       std::size_t len = (desired == (std::numeric_limits<std::size_t>::max)()) ? 0u : ::boost::re_detail::distance(position, last);
743       if(desired >= len)
744          end = last;
745       else
746          std::advance(end, desired);
747       BidiIterator origin(position);
748       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
749       {
750          ++position;
751       }
752       count = (unsigned)::boost::re_detail::distance(origin, position);
753    }
754    else
755    {
756       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
757       {
758          ++position;
759          ++count;
760       }
761    }
762    if((rep->leading) && (count < rep->max) && greedy)
763       restart = position;
764    if(count < rep->min)
765       return false;
766 
767    if(greedy)
768       return backtrack_till_match(count - rep->min);
769 
770    // non-greedy, keep trying till we get a match:
771    BidiIterator save_pos;
772    do
773    {
774       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
775       {
776          if(position != re_is_set_member(position, last, set, re.get_data(), icase))
777          {
778             ++position;
779             ++count;
780          }
781          else
782             return false;  // counldn't repeat even though it was the only option
783       }
784       if((rep->leading) && (rep->max == UINT_MAX))
785          restart = position;
786       pstate = rep->alt.p;
787       save_pos = position;
788       ++state_count;
789       if(match_all_states())
790          return true;
791       if(count >= rep->max)
792          return false;
793       position = save_pos;
794       if(position == last)
795          return false;
796       if(position != re_is_set_member(position, last, set, re.get_data(), icase))
797       {
798          ++position;
799          ++count;
800       }
801       else
802       {
803          return false;
804       }
805    }while(true);
806 #ifdef __BORLANDC__
807 #pragma option pop
808 #endif
809 #ifdef BOOST_MSVC
810 #pragma warning(pop)
811 #endif
812 }
813 
814 template <class BidiIterator, class Allocator, class traits>
backtrack_till_match(std::size_t count)815 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
816 {
817 #ifdef BOOST_MSVC
818 #pragma warning(push)
819 #pragma warning(disable:4127)
820 #endif
821    if((m_match_flags & match_partial) && (position == last))
822       m_has_partial_match = true;
823 
824    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
825    BidiIterator backtrack = position;
826    if(position == last)
827    {
828       if(rep->can_be_null & mask_skip)
829       {
830          pstate = rep->alt.p;
831          if(match_all_states())
832             return true;
833       }
834       if(count)
835       {
836          position = --backtrack;
837          --count;
838       }
839       else
840          return false;
841    }
842    do
843    {
844       while(count && !can_start(*position, rep->_map, mask_skip))
845       {
846          --position;
847          --count;
848          ++state_count;
849       }
850       pstate = rep->alt.p;
851       backtrack = position;
852       if(match_all_states())
853          return true;
854       if(count == 0)
855          return false;
856       position = --backtrack;
857       ++state_count;
858       --count;
859    }while(true);
860 #ifdef BOOST_MSVC
861 #pragma warning(pop)
862 #endif
863 }
864 
865 template <class BidiIterator, class Allocator, class traits>
match_recursion()866 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
867 {
868    BOOST_ASSERT(pstate->type == syntax_element_recurse);
869    //
870    // Set new call stack:
871    //
872    if(recursion_stack.capacity() == 0)
873    {
874       recursion_stack.reserve(50);
875    }
876    recursion_stack.push_back(recursion_info<results_type>());
877    recursion_stack.back().preturn_address = pstate->next.p;
878    recursion_stack.back().results = *m_presult;
879    recursion_stack.back().repeater_stack = next_count;
880    pstate = static_cast<const re_jump*>(pstate)->alt.p;
881    recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
882 
883    repeater_count<BidiIterator>* saved = next_count;
884    repeater_count<BidiIterator> r(&next_count); // resets all repeat counts since we're recursing and starting fresh on those
885    next_count = &r;
886    bool result = match_all_states();
887    next_count = saved;
888 
889    if(!result)
890    {
891       next_count = recursion_stack.back().repeater_stack;
892       *m_presult = recursion_stack.back().results;
893       recursion_stack.pop_back();
894       return false;
895    }
896    return true;
897 }
898 
899 template <class BidiIterator, class Allocator, class traits>
match_endmark()900 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
901 {
902    int index = static_cast<const re_brace*>(pstate)->index;
903    icase = static_cast<const re_brace*>(pstate)->icase;
904    if(index > 0)
905    {
906       if((m_match_flags & match_nosubs) == 0)
907       {
908          m_presult->set_second(position, index);
909       }
910       if(!recursion_stack.empty())
911       {
912          if(index == recursion_stack.back().idx)
913          {
914             recursion_info<results_type> saved = recursion_stack.back();
915             recursion_stack.pop_back();
916             pstate = saved.preturn_address;
917             repeater_count<BidiIterator>* saved_count = next_count;
918             next_count = saved.repeater_stack;
919             *m_presult = saved.results;
920             if(!match_all_states())
921             {
922                recursion_stack.push_back(saved);
923                next_count = saved_count;
924                return false;
925             }
926          }
927       }
928    }
929    else if((index < 0) && (index != -4))
930    {
931       // matched forward lookahead:
932       pstate = 0;
933       return true;
934    }
935    pstate = pstate ? pstate->next.p : 0;
936    return true;
937 }
938 
939 template <class BidiIterator, class Allocator, class traits>
match_match()940 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
941 {
942    if(!recursion_stack.empty())
943    {
944       BOOST_ASSERT(0 == recursion_stack.back().idx);
945       const re_syntax_base* saved_state = pstate = recursion_stack.back().preturn_address;
946       *m_presult = recursion_stack.back().results;
947       recursion_stack.pop_back();
948       if(!match_all_states())
949       {
950          recursion_stack.push_back(recursion_info<results_type>());
951          recursion_stack.back().preturn_address = saved_state;
952          recursion_stack.back().results = *m_presult;
953          return false;
954       }
955       return true;
956    }
957    if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
958       return false;
959    if((m_match_flags & match_all) && (position != last))
960       return false;
961    if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
962       return false;
963    m_presult->set_second(position);
964    pstate = 0;
965    m_has_found_match = true;
966    if((m_match_flags & match_posix) == match_posix)
967    {
968       m_result.maybe_assign(*m_presult);
969       if((m_match_flags & match_any) == 0)
970          return false;
971    }
972 #ifdef BOOST_REGEX_MATCH_EXTRA
973    if(match_extra & m_match_flags)
974    {
975       for(unsigned i = 0; i < m_presult->size(); ++i)
976          if((*m_presult)[i].matched)
977             ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
978    }
979 #endif
980    return true;
981 }
982 
983 
984 
985 } // namespace re_detail
986 } // namespace boost
987 #ifdef BOOST_MSVC
988 #pragma warning(pop)
989 #endif
990 
991 #ifdef BOOST_MSVC
992 #pragma warning(push)
993 #pragma warning(disable: 4103)
994 #endif
995 #ifdef BOOST_HAS_ABI_HEADERS
996 #  include BOOST_ABI_SUFFIX
997 #endif
998 #ifdef BOOST_MSVC
999 #pragma warning(pop)
1000 #endif
1001 
1002 #endif
1003 
1004