← Back to branch summary

~ubuntu-branches/ubuntu/wily/bombono-dvd/wily

« back to all changes in this revision

Viewing changes to libs/boost-lib/boost/regex/v4/perl_matcher_common.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Alessio Treglia
  • Date: 2010-11-04 11:46:25 UTC
  • mto: This revision was merged to the branch mainline in revision 8.
  • Revision ID: james.westby@ubuntu.com-20101104114625-8xfdhvhpsm51i0nu
Tags: upstream-0.8.0
Import upstream version 0.8.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
libs/boost-lib/boost/regex/v4/perl_matcher_common.hpp
20
20
#ifndef BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
21
21
#define BOOST_REGEX_V4_PERL_MATCHER_COMMON_HPP
22
22
 
 
23
#ifdef BOOST_MSVC
 
24
#pragma warning(push)
 
25
#pragma warning(disable: 4103)
 
26
#endif
23
27
#ifdef BOOST_HAS_ABI_HEADERS
24
28
#  include BOOST_ABI_PREFIX
25
29
#endif
 
30
#ifdef BOOST_MSVC
 
31
#pragma warning(pop)
 
32
#endif
26
33
 
27
34
#ifdef __BORLANDC__
28
35
#  pragma option push -w-8008 -w-8066
29
36
#endif
 
37
#ifdef BOOST_MSVC
 
38
#  pragma warning(push)
 
39
#  pragma warning(disable: 4800)
 
40
#endif
30
41
 
31
42
namespace boost{
32
43
namespace re_detail{
33
44
 
34
45
template <class BidiIterator, class Allocator, class traits>
35
 
perl_matcher<BidiIterator, Allocator, traits>::perl_matcher(BidiIterator first, BidiIterator end, 
36
 
   match_results<BidiIterator, Allocator>& what, 
37
 
   const basic_regex<char_type, traits>& e,
38
 
   match_flag_type f,
39
 
   BidiIterator b)
40
 
   :  m_result(what), base(first), last(end), 
41
 
      position(first), backstop(b), re(e), traits_inst(e.get_traits()), 
42
 
      m_independent(false), next_count(&rep_obj), rep_obj(&next_count)
43
 
{
44
 
   construct_init(e, f);
45
 
}
46
 
 
47
 
template <class BidiIterator, class Allocator, class traits>
48
46
void perl_matcher<BidiIterator, Allocator, traits>::construct_init(const basic_regex<char_type, traits>& e, match_flag_type f)
49
47
{ 
50
48
   typedef typename regex_iterator_traits<BidiIterator>::iterator_category category;
 
49
   typedef typename basic_regex<char_type, traits>::flag_type expression_flag_type;
51
50
   
52
51
   if(e.empty())
53
52
   {
57
56
   }
58
57
   pstate = 0;
59
58
   m_match_flags = f;
60
 
   icase = re.flags() & regex_constants::icase;
61
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
62
   if(!(m_match_flags & (match_perl|match_posix)))
63
63
   {
64
 
      if((re.flags() & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
 
64
      if((re_f & (regbase::main_option_type|regbase::no_perl_ex)) == 0)
65
65
         m_match_flags |= match_perl;
66
 
      else if((re.flags() & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
 
66
      else if((re_f & (regbase::main_option_type|regbase::emacs_ex)) == (regbase::basic_syntax_group|regbase::emacs_ex))
67
67
         m_match_flags |= match_perl;
68
68
      else
69
69
         m_match_flags |= match_posix;
80
80
   m_backup_state = 0;
81
81
#endif
82
82
   // find the value to use for matching word boundaries:
83
 
   const char_type w = static_cast<char_type>('w');
84
 
   m_word_mask = traits_inst.lookup_classname(&w, &w+1);
 
83
   m_word_mask = re.get_data().m_word_mask; 
85
84
   // find bitmask to use for matching '.':
86
85
   match_any_mask = static_cast<unsigned char>((f & match_not_dot_newline) ? re_detail::test_not_newline : re_detail::test_newline);
87
86
}
89
88
template <class BidiIterator, class Allocator, class traits>
90
89
void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(std::random_access_iterator_tag*)
91
90
{
92
 
   static const difference_type k = 100000;
93
 
   difference_type dist = boost::re_detail::distance(base, last);
94
 
   traits_size_type states = static_cast<traits_size_type>(re.size());
 
91
   //
 
92
   // How many states should we allow our machine to visit before giving up?
 
93
   // This is a heuristic: it takes the greater of O(N^2) and O(NS^2)
 
94
   // where N is the length of the string, and S is the number of states
 
95
   // in the machine.  It's tempting to up this to O(N^2S) or even O(N^2S^2)
 
96
   // but these take unreasonably amounts of time to bale out in pathological
 
97
   // cases.
 
98
   //
 
99
   // Calculate NS^2 first:
 
100
   //
 
101
   static const std::ptrdiff_t k = 100000;
 
102
   std::ptrdiff_t dist = boost::re_detail::distance(base, last);
 
103
   if(dist == 0)
 
104
      dist = 1;
 
105
   std::ptrdiff_t states = re.size();
 
106
   if(states == 0)
 
107
      states = 1;
95
108
   states *= states;
96
 
   difference_type lim = ((std::numeric_limits<difference_type>::max)() - k) / states;
97
 
   if(dist >= lim)
98
 
      max_state_count = (std::numeric_limits<difference_type>::max)();
99
 
   else
100
 
      max_state_count = k + states * dist;
 
109
   if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
 
110
   {
 
111
      max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 
112
      return;
 
113
   }
 
114
   states *= dist;
 
115
   if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
 
116
   {
 
117
      max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 
118
      return;
 
119
   }
 
120
   states += k;
 
121
 
 
122
   max_state_count = states;
 
123
 
 
124
   //
 
125
   // Now calculate N^2:
 
126
   //
 
127
   states = dist;
 
128
   if((std::numeric_limits<std::ptrdiff_t>::max)() / dist < states)
 
129
   {
 
130
      max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 
131
      return;
 
132
   }
 
133
   states *= dist;
 
134
   if((std::numeric_limits<std::ptrdiff_t>::max)() - k < states)
 
135
   {
 
136
      max_state_count = (std::min)((std::ptrdiff_t)BOOST_REGEX_MAX_STATE_COUNT, (std::numeric_limits<std::ptrdiff_t>::max)() - 2);
 
137
      return;
 
138
   }
 
139
   states += k;
 
140
   //
 
141
   // N^2 can be a very large number indeed, to prevent things getting out
 
142
   // of control, cap the max states:
 
143
   //
 
144
   if(states > BOOST_REGEX_MAX_STATE_COUNT)
 
145
      states = BOOST_REGEX_MAX_STATE_COUNT;
 
146
   //
 
147
   // If (the possibly capped) N^2 is larger than our first estimate,
 
148
   // use this instead:
 
149
   //
 
150
   if(states > max_state_count)
 
151
      max_state_count = states;
101
152
}
102
153
 
103
154
template <class BidiIterator, class Allocator, class traits>
104
 
void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
 
155
inline void perl_matcher<BidiIterator, Allocator, traits>::estimate_max_state_count(void*)
105
156
{
106
157
   // we don't know how long the sequence is:
107
158
   max_state_count = BOOST_REGEX_MAX_STATE_COUNT;
109
160
 
110
161
#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
111
162
template <class BidiIterator, class Allocator, class traits>
112
 
bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
 
163
inline bool perl_matcher<BidiIterator, Allocator, traits>::protected_call(
113
164
   protected_proc_type proc)
114
165
{
115
 
   /*
116
 
   __try{
117
 
      return (this->*proc)();
118
 
   }__except(EXCEPTION_STACK_OVERFLOW == GetExceptionCode())
119
 
   {
120
 
      reset_stack_guard_page();
121
 
   }
122
 
   // we only get here after a stack overflow:
123
 
   raise_error<traits>(traits_inst, regex_constants::error_size);
124
 
   // and we never really get here at all:
125
 
   return false;
126
 
   */
127
166
   ::boost::re_detail::concrete_protected_call
128
167
      <perl_matcher<BidiIterator, Allocator, traits> >
129
168
      obj(this, proc);
133
172
#endif
134
173
 
135
174
template <class BidiIterator, class Allocator, class traits>
136
 
bool perl_matcher<BidiIterator, Allocator, traits>::match()
 
175
inline bool perl_matcher<BidiIterator, Allocator, traits>::match()
137
176
{
138
177
#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
139
178
   return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::match_imp);
161
200
   m_match_flags |= regex_constants::match_all;
162
201
   m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), search_base, last);
163
202
   m_presult->set_base(base);
 
203
   m_presult->set_named_subs(re_detail::convert_to_named_subs<typename match_results<BidiIterator>::char_type>(this->re.get_named_subs()));
164
204
   if(m_match_flags & match_posix)
165
205
      m_result = *m_presult;
166
206
   verify_options(re.flags(), m_match_flags);
167
207
   if(0 == match_prefix())
168
208
      return false;
169
 
   return m_result[0].second == last;
 
209
   return (m_result[0].second == last) && (m_result[0].first == base);
170
210
 
171
211
#if defined(BOOST_REGEX_NON_RECURSIVE) && !defined(BOOST_NO_EXCEPTIONS)
172
212
   }
182
222
}
183
223
 
184
224
template <class BidiIterator, class Allocator, class traits>
185
 
bool perl_matcher<BidiIterator, Allocator, traits>::find()
 
225
inline bool perl_matcher<BidiIterator, Allocator, traits>::find()
186
226
{
187
227
#ifdef BOOST_REGEX_HAS_MS_STACK_GUARD
188
228
   return protected_call(&perl_matcher<BidiIterator, Allocator, traits>::find_imp);
222
262
      pstate = re.get_first_state();
223
263
      m_presult->set_size((m_match_flags & match_nosubs) ? 1 : re.mark_count(), base, last);
224
264
      m_presult->set_base(base);
 
265
      m_presult->set_named_subs(re_detail::convert_to_named_subs<typename match_results<BidiIterator>::char_type>(this->re.get_named_subs()));
225
266
      m_match_flags |= regex_constants::match_init;
226
267
   }
227
268
   else
305
346
}
306
347
 
307
348
template <class BidiIterator, class Allocator, class traits>
308
 
bool perl_matcher<BidiIterator, Allocator, traits>::match_endmark()
309
 
{
310
 
   int index = static_cast<const re_brace*>(pstate)->index;
311
 
   if(index > 0)
312
 
   {
313
 
      if((m_match_flags & match_nosubs) == 0)
314
 
         m_presult->set_second(position, index);
315
 
   }
316
 
   else if((index < 0) && (index != -4))
317
 
   {
318
 
      // matched forward lookahead:
319
 
      pstate = 0;
320
 
      return true;
321
 
   }
322
 
   pstate = pstate->next.p;
323
 
   return true;
324
 
}
325
 
 
326
 
template <class BidiIterator, class Allocator, class traits>
327
349
bool perl_matcher<BidiIterator, Allocator, traits>::match_literal()
328
350
{
329
351
   unsigned int len = static_cast<const re_literal*>(pstate)->length;
424
446
}
425
447
 
426
448
template <class BidiIterator, class Allocator, class traits>
427
 
bool perl_matcher<BidiIterator, Allocator, traits>::match_match()
428
 
{
429
 
   if((m_match_flags & match_not_null) && (position == (*m_presult)[0].first))
430
 
      return false;
431
 
   if((m_match_flags & match_all) && (position != last))
432
 
      return false;
433
 
   if((m_match_flags & regex_constants::match_not_initial_null) && (position == search_base))
434
 
      return false;
435
 
   m_presult->set_second(position);
436
 
   pstate = 0;
437
 
   m_has_found_match = true;
438
 
   if((m_match_flags & match_posix) == match_posix)
439
 
   {
440
 
      m_result.maybe_assign(*m_presult);
441
 
      if((m_match_flags & match_any) == 0)
442
 
         return false;
443
 
   }
444
 
#ifdef BOOST_REGEX_MATCH_EXTRA
445
 
   if(match_extra & m_match_flags)
446
 
   {
447
 
      for(unsigned i = 0; i < m_presult->size(); ++i)
448
 
         if((*m_presult)[i].matched)
449
 
            ((*m_presult)[i]).get_captures().push_back((*m_presult)[i]);
450
 
   }
451
 
#endif
452
 
   return true;
453
 
}
454
 
 
455
 
template <class BidiIterator, class Allocator, class traits>
456
449
bool perl_matcher<BidiIterator, Allocator, traits>::match_word_boundary()
457
450
{
458
451
   bool b; // indcates whether next character is a word character
496
489
   if(position == last)
497
490
      return false;
498
491
   // both prev and this character must be m_word_mask:
499
 
   if(traits_inst.isctype(*position, m_word_mask))
 
492
   bool prev = traits_inst.isctype(*position, m_word_mask);
500
493
   {
501
494
      bool b;
502
495
      if((position == backstop) && ((m_match_flags & match_prev_avail) == 0)) 
507
500
         b = traits_inst.isctype(*position, m_word_mask);
508
501
         ++position;
509
502
      }
510
 
      if(b)
 
503
      if(b == prev)
511
504
      {
512
505
         pstate = pstate->next.p;
513
506
         return true;
589
582
template <class BidiIterator, class Allocator, class traits>
590
583
bool perl_matcher<BidiIterator, Allocator, traits>::match_backref()
591
584
{
592
 
   // compare with what we previously matched:
 
585
   //
 
586
   // Compare with what we previously matched.
 
587
   // Note that this succeeds if the backref did not partisipate
 
588
   // in the match, this is in line with ECMAScript, but not Perl
 
589
   // or PCRE.
 
590
   //
593
591
   BidiIterator i = (*m_presult)[static_cast<const re_brace*>(pstate)->index].first;
594
592
   BidiIterator j = (*m_presult)[static_cast<const re_brace*>(pstate)->index].second;
595
593
   while(i != j)
714
712
inline bool perl_matcher<BidiIterator, Allocator, traits>::match_assert_backref()
715
713
{
716
714
   // return true if marked sub-expression N has been matched:
717
 
   bool result = (*m_presult)[static_cast<const re_brace*>(pstate)->index].matched;
718
 
   pstate = pstate->next.p;
 
715
   int index = static_cast<const re_brace*>(pstate)->index;
 
716
   bool result;
 
717
   if(index == 9999)
 
718
   {
 
719
      // Magic value for a (DEFINE) block:
 
720
      return false;
 
721
   }
 
722
   else if(index > 0)
 
723
   {
 
724
      // Check if index is a hash value:
 
725
      if(index >= 10000)
 
726
         index = re.get_data().get_id(index);
 
727
      // Have we matched subexpression "index"?
 
728
      result = (*m_presult)[index].matched;
 
729
      pstate = pstate->next.p;
 
730
   }
 
731
   else
 
732
   {
 
733
      // Have we recursed into subexpression "index"?
 
734
      // If index == 0 then check for any recursion at all, otherwise for recursion to -index-1.
 
735
      int idx = -index-1;
 
736
      if(idx >= 10000)
 
737
         idx = re.get_data().get_id(idx);
 
738
      result = !recursion_stack.empty() && ((recursion_stack.back().idx == idx) || (index == 0));
 
739
      pstate = pstate->next.p;
 
740
   }
719
741
   return result;
720
742
}
721
743
 
905
927
 
906
928
} // namespace boost
907
929
 
 
930
#ifdef BOOST_MSVC
 
931
#  pragma warning(pop)
 
932
#endif
 
933
 
908
934
#ifdef __BORLANDC__
909
935
#  pragma option pop
910
936
#endif
 
937
#ifdef BOOST_MSVC
 
938
#pragma warning(push)
 
939
#pragma warning(disable: 4103)
 
940
#endif
911
941
#ifdef BOOST_HAS_ABI_HEADERS
912
942
#  include BOOST_ABI_SUFFIX
913
943
#endif
 
944
#ifdef BOOST_MSVC
 
945
#pragma warning(pop)
 
946
#endif
914
947
 
915
948
#endif
916
949