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       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
645       BidiIterator origin(position);
646       while((position != end) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
647       {
648          ++position;
649       }
650       count = (unsigned)::boost::re_detail::distance(origin, position);
651    }
652    else
653    {
654       while((count < desired) && (position != last) && map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
655       {
656          ++position;
657          ++count;
658       }
659    }
660    if((rep->leading) && (count < rep->max) && greedy)
661       restart = position;
662    if(count < rep->min)
663       return false;
664 
665    if(greedy)
666       return backtrack_till_match(count - rep->min);
667 
668    // non-greedy, keep trying till we get a match:
669    BidiIterator save_pos;
670    do
671    {
672       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
673       {
674          if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
675          {
676             ++position;
677             ++count;
678          }
679          else
680             return false;  // counldn't repeat even though it was the only option
681       }
682       if((rep->leading) && (rep->max == UINT_MAX))
683          restart = position;
684       pstate = rep->alt.p;
685       save_pos = position;
686       ++state_count;
687       if(match_all_states())
688          return true;
689       if(count >= rep->max)
690          return false;
691       position = save_pos;
692       if(position == last)
693          return false;
694       if(map[static_cast<unsigned char>(traits_inst.translate(*position, icase))])
695       {
696          ++position;
697          ++count;
698       }
699       else
700       {
701          return false;
702       }
703    }while(true);
704 #ifdef __BORLANDC__
705 #pragma option pop
706 #endif
707 #ifdef BOOST_MSVC
708 #pragma warning(pop)
709 #endif
710 }
711 
712 template <class BidiIterator, class Allocator, class traits>
match_long_set_repeat()713 bool perl_matcher<BidiIterator, Allocator, traits>::match_long_set_repeat()
714 {
715 #ifdef BOOST_MSVC
716 #pragma warning(push)
717 #pragma warning(disable:4127)
718 #endif
719 #ifdef __BORLANDC__
720 #pragma option push -w-8008 -w-8066 -w-8004
721 #endif
722    typedef typename traits::char_class_type char_class_type;
723    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
724    const re_set_long<char_class_type>* set = static_cast<const re_set_long<char_class_type>*>(pstate->next.p);
725    unsigned count = 0;
726    //
727    // start by working out how much we can skip:
728    //
729    bool greedy = (rep->greedy) && (!(m_match_flags & regex_constants::match_any) || m_independent);
730    std::size_t desired = greedy ? rep->max : rep->min;
731    if(::boost::is_random_access_iterator<BidiIterator>::value)
732    {
733       BidiIterator end = position;
734       std::advance(end, (std::min)((std::size_t)::boost::re_detail::distance(position, last), desired));
735       BidiIterator origin(position);
736       while((position != end) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
737       {
738          ++position;
739       }
740       count = (unsigned)::boost::re_detail::distance(origin, position);
741    }
742    else
743    {
744       while((count < desired) && (position != last) && (position != re_is_set_member(position, last, set, re.get_data(), icase)))
745       {
746          ++position;
747          ++count;
748       }
749    }
750    if((rep->leading) && (count < rep->max) && greedy)
751       restart = position;
752    if(count < rep->min)
753       return false;
754 
755    if(greedy)
756       return backtrack_till_match(count - rep->min);
757 
758    // non-greedy, keep trying till we get a match:
759    BidiIterator save_pos;
760    do
761    {
762       while((position != last) && (count < rep->max) && !can_start(*position, rep->_map, mask_skip))
763       {
764          if(position != re_is_set_member(position, last, set, re.get_data(), icase))
765          {
766             ++position;
767             ++count;
768          }
769          else
770             return false;  // counldn't repeat even though it was the only option
771       }
772       if((rep->leading) && (rep->max == UINT_MAX))
773          restart = position;
774       pstate = rep->alt.p;
775       save_pos = position;
776       ++state_count;
777       if(match_all_states())
778          return true;
779       if(count >= rep->max)
780          return false;
781       position = save_pos;
782       if(position == last)
783          return false;
784       if(position != re_is_set_member(position, last, set, re.get_data(), icase))
785       {
786          ++position;
787          ++count;
788       }
789       else
790       {
791          return false;
792       }
793    }while(true);
794 #ifdef __BORLANDC__
795 #pragma option pop
796 #endif
797 #ifdef BOOST_MSVC
798 #pragma warning(pop)
799 #endif
800 }
801 
802 template <class BidiIterator, class Allocator, class traits>
backtrack_till_match(std::size_t count)803 bool perl_matcher<BidiIterator, Allocator, traits>::backtrack_till_match(std::size_t count)
804 {
805 #ifdef BOOST_MSVC
806 #pragma warning(push)
807 #pragma warning(disable:4127)
808 #endif
809    if((m_match_flags & match_partial) && (position == last))
810       m_has_partial_match = true;
811 
812    const re_repeat* rep = static_cast<const re_repeat*>(pstate);
813    BidiIterator backtrack = position;
814    if(position == last)
815    {
816       if(rep->can_be_null & mask_skip)
817       {
818          pstate = rep->alt.p;
819          if(match_all_states())
820             return true;
821       }
822       if(count)
823       {
824          position = --backtrack;
825          --count;
826       }
827       else
828          return false;
829    }
830    do
831    {
832       while(count && !can_start(*position, rep->_map, mask_skip))
833       {
834          --position;
835          --count;
836          ++state_count;
837       }
838       pstate = rep->alt.p;
839       backtrack = position;
840       if(match_all_states())
841          return true;
842       if(count == 0)
843          return false;
844       position = --backtrack;
845       ++state_count;
846       --count;
847    }while(true);
848 #ifdef BOOST_MSVC
849 #pragma warning(pop)
850 #endif
851 }
852 
853 template <class BidiIterator, class Allocator, class traits>
match_recursion()854 bool perl_matcher<BidiIterator, Allocator, traits>::match_recursion()
855 {
856    BOOST_ASSERT(pstate->type == syntax_element_recurse);
857    //
858    // Set new call stack:
859    //
860    if(recursion_stack.capacity() == 0)
861    {
862       recursion_stack.reserve(50);
863    }
864    recursion_stack.push_back(recursion_info<results_type>());
865    recursion_stack.back().preturn_address = pstate->next.p;
866    recursion_stack.back().results = *m_presult;
867    recursion_stack.back().repeater_stack = next_count;
868    pstate = static_cast<const re_jump*>(pstate)->alt.p;
869    recursion_stack.back().idx = static_cast<const re_brace*>(pstate)->index;
870 
871    repeater_count<BidiIterator>* saved = next_count;
872    repeater_count<BidiIterator> r(&next_count); // resets all repeat counts since we're recursing and starting fresh on those
873    next_count = &r;
874    bool result = match_all_states();
875    next_count = saved;
876 
877    if(!result)
878    {
879       next_count = recursion_stack.back().repeater_stack;
880       *m_presult = recursion_stack.back().results;
881       recursion_stack.pop_back();
882       return false;
883    }
884    return true;
885 }
886 
887 template <class BidiIterator, class Allocator, class traits>
match_endmark()888 bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
889 {
890    int index = static_cast<const re_brace*>(pstate)->index;
891    icase = static_cast<const re_brace*>(pstate)->icase;
892    if(index > 0)
893    {
894       if((m_match_flags & match_nosubs) == 0)
895       {
896          m_presult->set_second(position, index);
897       }
898       if(!recursion_stack.empty())
899       {
900          if(index == recursion_stack.back().idx)
901          {
902             recursion_info<results_type> saved = recursion_stack.back();
903             recursion_stack.pop_back();
904             pstate = saved.preturn_address;
905             repeater_count<BidiIterator>* saved_count = next_count;
906             next_count = saved.repeater_stack;
907             *m_presult = saved.results;
908             if(!match_all_states())
909             {
910                recursion_stack.push_back(saved);
911                next_count = saved_count;
912                return false;
913             }
914          }
915       }
916    }
917    else if((index < 0) && (index != -4))
918    {
919       // matched forward lookahead:
920       pstate = 0;
921       return true;
922    }
923    pstate = pstate ? pstate->next.p : 0;
924    return true;
925 }
926 
927 template <class BidiIterator, class Allocator, class traits>
match_match()928 bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
929 {
930    if(!recursion_stack.empty())
931    {
932       BOOST_ASSERT(0 == recursion_stack.back().idx);
933       const re_syntax_base* saved_state = pstate = recursion_stack.back().preturn_address;
934       *m_presult = recursion_stack.back().results;
935       recursion_stack.pop_back();
936       if(!match_all_states())
937       {
938          recursion_stack.push_back(recursion_info<results_type>());
939          recursion_stack.back().preturn_address = saved_state;
940          recursion_stack.back().results = *m_presult;
941          return false;
942       }
943       return true;
944    }
945    if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
946       return false;
947    if((m_match_flags & match_all) && (position != last))
948       return false;
949    if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
950       return false;
951    m_presult->set_second(position);
952    pstate = 0;
953    m_has_found_match = true;
954    if((m_match_flags & match_posix) == match_posix)
955    {
956       m_result.maybe_assign(*m_presult);
957       if((m_match_flags & match_any) == 0)
958          return false;
959    }
960 #ifdef BOOST_REGEX_MATCH_EXTRA
961    if(match_extra & m_match_flags)
962    {
963       for(unsigned i = 0; i < m_presult->size(); ++i)
964          if((*m_presult)[i].matched)
965             ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
966    }
967 #endif
968    return true;
969 }
970 
971 
972 
973 } // namespace re_detail
974 } // namespace boost
975 #ifdef BOOST_MSVC
976 #pragma warning(pop)
977 #endif
978 
979 #ifdef BOOST_MSVC
980 #pragma warning(push)
981 #pragma warning(disable: 4103)
982 #endif
983 #ifdef BOOST_HAS_ABI_HEADERS
984 #  include BOOST_ABI_SUFFIX
985 #endif
986 #ifdef BOOST_MSVC
987 #pragma warning(pop)
988 #endif
989 
990 #endif
991 
992