1/*
2 *
3 * Copyright (c) 2004
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 basic_regex_creator.cpp
15 * VERSION see <boost/version.hpp>
16 * DESCRIPTION: Declares template class basic_regex_creator which fills in
17 * the data members of a regex_data object.
18 */
19
20#ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
21#define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_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
39namespace boost{
40
41namespace BOOST_REGEX_DETAIL_NS{
42
43template <class charT>
44struct digraph : public std::pair<charT, charT>
45{
46 digraph() : std::pair<charT, charT>(0, 0){}
47 digraph(charT c1) : std::pair<charT, charT>(c1, 0){}
48 digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
49 {}
50 digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
51 template <class Seq>
52 digraph(const Seq& s) : std::pair<charT, charT>()
53 {
54 BOOST_ASSERT(s.size() <= 2);
55 BOOST_ASSERT(s.size());
56 this->first = s[0];
57 this->second = (s.size() > 1) ? s[1] : 0;
58 }
59};
60
61template <class charT, class traits>
62class basic_char_set
63{
64public:
65 typedef digraph<charT> digraph_type;
66 typedef typename traits::string_type string_type;
67 typedef typename traits::char_class_type m_type;
68
69 basic_char_set()
70 {
71 m_negate = false;
72 m_has_digraphs = false;
73 m_classes = 0;
74 m_negated_classes = 0;
75 m_empty = true;
76 }
77
78 void add_single(const digraph_type& s)
79 {
80 m_singles.insert(s);
81 if(s.second)
82 m_has_digraphs = true;
83 m_empty = false;
84 }
85 void add_range(const digraph_type& first, const digraph_type& end)
86 {
87 m_ranges.push_back(first);
88 m_ranges.push_back(end);
89 if(first.second)
90 {
91 m_has_digraphs = true;
92 add_single(first);
93 }
94 if(end.second)
95 {
96 m_has_digraphs = true;
97 add_single(end);
98 }
99 m_empty = false;
100 }
101 void add_class(m_type m)
102 {
103 m_classes |= m;
104 m_empty = false;
105 }
106 void add_negated_class(m_type m)
107 {
108 m_negated_classes |= m;
109 m_empty = false;
110 }
111 void add_equivalent(const digraph_type& s)
112 {
113 m_equivalents.insert(s);
114 if(s.second)
115 {
116 m_has_digraphs = true;
117 add_single(s);
118 }
119 m_empty = false;
120 }
121 void negate()
122 {
123 m_negate = true;
124 //m_empty = false;
125 }
126
127 //
128 // accessor functions:
129 //
130 bool has_digraphs()const
131 {
132 return m_has_digraphs;
133 }
134 bool is_negated()const
135 {
136 return m_negate;
137 }
138 typedef typename std::vector<digraph_type>::const_iterator list_iterator;
139 typedef typename std::set<digraph_type>::const_iterator set_iterator;
140 set_iterator singles_begin()const
141 {
142 return m_singles.begin();
143 }
144 set_iterator singles_end()const
145 {
146 return m_singles.end();
147 }
148 list_iterator ranges_begin()const
149 {
150 return m_ranges.begin();
151 }
152 list_iterator ranges_end()const
153 {
154 return m_ranges.end();
155 }
156 set_iterator equivalents_begin()const
157 {
158 return m_equivalents.begin();
159 }
160 set_iterator equivalents_end()const
161 {
162 return m_equivalents.end();
163 }
164 m_type classes()const
165 {
166 return m_classes;
167 }
168 m_type negated_classes()const
169 {
170 return m_negated_classes;
171 }
172 bool empty()const
173 {
174 return m_empty;
175 }
176private:
177 std::set<digraph_type> m_singles; // a list of single characters to match
178 std::vector<digraph_type> m_ranges; // a list of end points of our ranges
179 bool m_negate; // true if the set is to be negated
180 bool m_has_digraphs; // true if we have digraphs present
181 m_type m_classes; // character classes to match
182 m_type m_negated_classes; // negated character classes to match
183 bool m_empty; // whether we've added anything yet
184 std::set<digraph_type> m_equivalents; // a list of equivalence classes
185};
186
187template <class charT, class traits>
188class basic_regex_creator
189{
190public:
191 basic_regex_creator(regex_data<charT, traits>* data);
192 std::ptrdiff_t getoffset(void* addr)
193 {
194 return getoffset(addr, m_pdata->m_data.data());
195 }
196 std::ptrdiff_t getoffset(const void* addr, const void* base)
197 {
198 return static_cast<const char*>(addr) - static_cast<const char*>(base);
199 }
200 re_syntax_base* getaddress(std::ptrdiff_t off)
201 {
202 return getaddress(off, m_pdata->m_data.data());
203 }
204 re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
205 {
206 return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
207 }
208 void init(unsigned l_flags)
209 {
210 m_pdata->m_flags = l_flags;
211 m_icase = l_flags & regex_constants::icase;
212 }
213 regbase::flag_type flags()
214 {
215 return m_pdata->m_flags;
216 }
217 void flags(regbase::flag_type f)
218 {
219 m_pdata->m_flags = f;
220 if(m_icase != static_cast<bool>(f & regbase::icase))
221 {
222 m_icase = static_cast<bool>(f & regbase::icase);
223 }
224 }
225 re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
226 re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
227 re_literal* append_literal(charT c);
228 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
229 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
230 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
231 void finalize(const charT* p1, const charT* p2);
232protected:
233 regex_data<charT, traits>* m_pdata; // pointer to the basic_regex_data struct we are filling in
234 const ::boost::regex_traits_wrapper<traits>&
235 m_traits; // convenience reference to traits class
236 re_syntax_base* m_last_state; // the last state we added
237 bool m_icase; // true for case insensitive matches
238 unsigned m_repeater_id; // the state_id of the next repeater
239 bool m_has_backrefs; // true if there are actually any backrefs
240 unsigned m_backrefs; // bitmask of permitted backrefs
241 boost::uintmax_t m_bad_repeats; // bitmask of repeats we can't deduce a startmap for;
242 bool m_has_recursions; // set when we have recursive expresisons to fixup
243 std::vector<unsigned char> m_recursion_checks; // notes which recursions we've followed while analysing this expression
244 typename traits::char_class_type m_word_mask; // mask used to determine if a character is a word character
245 typename traits::char_class_type m_mask_space; // mask used to determine if a character is a word character
246 typename traits::char_class_type m_lower_mask; // mask used to determine if a character is a lowercase character
247 typename traits::char_class_type m_upper_mask; // mask used to determine if a character is an uppercase character
248 typename traits::char_class_type m_alpha_mask; // mask used to determine if a character is an alphabetic character
249private:
250 basic_regex_creator& operator=(const basic_regex_creator&);
251 basic_regex_creator(const basic_regex_creator&);
252
253 void fixup_pointers(re_syntax_base* state);
254 void fixup_recursions(re_syntax_base* state);
255 void create_startmaps(re_syntax_base* state);
256 int calculate_backstep(re_syntax_base* state);
257 void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
258 unsigned get_restart_type(re_syntax_base* state);
259 void set_all_masks(unsigned char* bits, unsigned char);
260 bool is_bad_repeat(re_syntax_base* pt);
261 void set_bad_repeat(re_syntax_base* pt);
262 syntax_element_type get_repeat_type(re_syntax_base* state);
263 void probe_leading_repeat(re_syntax_base* state);
264};
265
266template <class charT, class traits>
267basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
268 : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_repeater_id(0), m_has_backrefs(false), m_backrefs(0), m_has_recursions(false)
269{
270 m_pdata->m_data.clear();
271 m_pdata->m_status = ::boost::regex_constants::error_ok;
272 static const charT w = 'w';
273 static const charT s = 's';
274 static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
275 static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
276 static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
277 m_word_mask = m_traits.lookup_classname(&w, &w +1);
278 m_mask_space = m_traits.lookup_classname(&s, &s +1);
279 m_lower_mask = m_traits.lookup_classname(l, l + 5);
280 m_upper_mask = m_traits.lookup_classname(u, u + 5);
281 m_alpha_mask = m_traits.lookup_classname(a, a + 5);
282 m_pdata->m_word_mask = m_word_mask;
283 BOOST_ASSERT(m_word_mask != 0);
284 BOOST_ASSERT(m_mask_space != 0);
285 BOOST_ASSERT(m_lower_mask != 0);
286 BOOST_ASSERT(m_upper_mask != 0);
287 BOOST_ASSERT(m_alpha_mask != 0);
288}
289
290template <class charT, class traits>
291re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
292{
293 // if the state is a backref then make a note of it:
294 if(t == syntax_element_backref)
295 this->m_has_backrefs = true;
296 // append a new state, start by aligning our last one:
297 m_pdata->m_data.align();
298 // set the offset to the next state in our last one:
299 if(m_last_state)
300 m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
301 // now actually extent our data:
302 m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
303 // fill in boilerplate options in the new state:
304 m_last_state->next.i = 0;
305 m_last_state->type = t;
306 return m_last_state;
307}
308
309template <class charT, class traits>
310re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
311{
312 // append a new state, start by aligning our last one:
313 m_pdata->m_data.align();
314 // set the offset to the next state in our last one:
315 if(m_last_state)
316 m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
317 // remember the last state position:
318 std::ptrdiff_t off = getoffset(m_last_state) + s;
319 // now actually insert our data:
320 re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
321 // fill in boilerplate options in the new state:
322 new_state->next.i = s;
323 new_state->type = t;
324 m_last_state = getaddress(off);
325 return new_state;
326}
327
328template <class charT, class traits>
329re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
330{
331 re_literal* result;
332 // start by seeing if we have an existing re_literal we can extend:
333 if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
334 {
335 // no existing re_literal, create a new one:
336 result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
337 result->length = 1;
338 *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
339 }
340 else
341 {
342 // we have an existing re_literal, extend it:
343 std::ptrdiff_t off = getoffset(m_last_state);
344 m_pdata->m_data.extend(sizeof(charT));
345 m_last_state = result = static_cast<re_literal*>(getaddress(off));
346 charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
347 characters[result->length] = m_traits.translate(c, m_icase);
348 result->length += 1;
349 }
350 return result;
351}
352
353template <class charT, class traits>
354inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
355 const basic_char_set<charT, traits>& char_set)
356{
357 typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
358 return char_set.has_digraphs()
359 ? append_set(char_set, static_cast<mpl::false_*>(0))
360 : append_set(char_set, static_cast<truth_type*>(0));
361}
362
363template <class charT, class traits>
364re_syntax_base* basic_regex_creator<charT, traits>::append_set(
365 const basic_char_set<charT, traits>& char_set, mpl::false_*)
366{
367 typedef typename traits::string_type string_type;
368 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
369 typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
370 typedef typename traits::char_class_type m_type;
371
372 re_set_long<m_type>* result = static_cast<re_set_long<m_type>*>(append_state(syntax_element_long_set, sizeof(re_set_long<m_type>)));
373 //
374 // fill in the basics:
375 //
376 result->csingles = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.singles_begin(), char_set.singles_end()));
377 result->cranges = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
378 result->cequivalents = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
379 result->cclasses = char_set.classes();
380 result->cnclasses = char_set.negated_classes();
381 if(flags() & regbase::icase)
382 {
383 // adjust classes as needed:
384 if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
385 result->cclasses |= m_alpha_mask;
386 if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
387 result->cnclasses |= m_alpha_mask;
388 }
389
390 result->isnot = char_set.is_negated();
391 result->singleton = !char_set.has_digraphs();
392 //
393 // remember where the state is for later:
394 //
395 std::ptrdiff_t offset = getoffset(result);
396 //
397 // now extend with all the singles:
398 //
399 item_iterator first, last;
400 set_iterator sfirst, slast;
401 sfirst = char_set.singles_begin();
402 slast = char_set.singles_end();
403 while(sfirst != slast)
404 {
405 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (sfirst->first == static_cast<charT>(0) ? 1 : sfirst->second ? 3 : 2)));
406 p[0] = m_traits.translate(sfirst->first, m_icase);
407 if(sfirst->first == static_cast<charT>(0))
408 {
409 p[0] = 0;
410 }
411 else if(sfirst->second)
412 {
413 p[1] = m_traits.translate(sfirst->second, m_icase);
414 p[2] = 0;
415 }
416 else
417 p[1] = 0;
418 ++sfirst;
419 }
420 //
421 // now extend with all the ranges:
422 //
423 first = char_set.ranges_begin();
424 last = char_set.ranges_end();
425 while(first != last)
426 {
427 // first grab the endpoints of the range:
428 digraph<charT> c1 = *first;
429 c1.first = this->m_traits.translate(c1.first, this->m_icase);
430 c1.second = this->m_traits.translate(c1.second, this->m_icase);
431 ++first;
432 digraph<charT> c2 = *first;
433 c2.first = this->m_traits.translate(c2.first, this->m_icase);
434 c2.second = this->m_traits.translate(c2.second, this->m_icase);
435 ++first;
436 string_type s1, s2;
437 // different actions now depending upon whether collation is turned on:
438 if(flags() & regex_constants::collate)
439 {
440 // we need to transform our range into sort keys:
441 charT a1[3] = { c1.first, c1.second, charT(0), };
442 charT a2[3] = { c2.first, c2.second, charT(0), };
443 s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
444 s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
445 if(s1.size() == 0)
446 s1 = string_type(1, charT(0));
447 if(s2.size() == 0)
448 s2 = string_type(1, charT(0));
449 }
450 else
451 {
452 if(c1.second)
453 {
454 s1.insert(s1.end(), c1.first);
455 s1.insert(s1.end(), c1.second);
456 }
457 else
458 s1 = string_type(1, c1.first);
459 if(c2.second)
460 {
461 s2.insert(s2.end(), c2.first);
462 s2.insert(s2.end(), c2.second);
463 }
464 else
465 s2.insert(s2.end(), c2.first);
466 }
467 if(s1 > s2)
468 {
469 // Oops error:
470 return 0;
471 }
472 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
473 BOOST_REGEX_DETAIL_NS::copy(s1.begin(), s1.end(), p);
474 p[s1.size()] = charT(0);
475 p += s1.size() + 1;
476 BOOST_REGEX_DETAIL_NS::copy(s2.begin(), s2.end(), p);
477 p[s2.size()] = charT(0);
478 }
479 //
480 // now process the equivalence classes:
481 //
482 sfirst = char_set.equivalents_begin();
483 slast = char_set.equivalents_end();
484 while(sfirst != slast)
485 {
486 string_type s;
487 if(sfirst->second)
488 {
489 charT cs[3] = { sfirst->first, sfirst->second, charT(0), };
490 s = m_traits.transform_primary(cs, cs+2);
491 }
492 else
493 s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
494 if(s.empty())
495 return 0; // invalid or unsupported equivalence class
496 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
497 BOOST_REGEX_DETAIL_NS::copy(s.begin(), s.end(), p);
498 p[s.size()] = charT(0);
499 ++sfirst;
500 }
501 //
502 // finally reset the address of our last state:
503 //
504 m_last_state = result = static_cast<re_set_long<m_type>*>(getaddress(offset));
505 return result;
506}
507
508template<class T>
509inline bool char_less(T t1, T t2)
510{
511 return t1 < t2;
512}
513inline bool char_less(char t1, char t2)
514{
515 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
516}
517inline bool char_less(signed char t1, signed char t2)
518{
519 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
520}
521
522template <class charT, class traits>
523re_syntax_base* basic_regex_creator<charT, traits>::append_set(
524 const basic_char_set<charT, traits>& char_set, mpl::true_*)
525{
526 typedef typename traits::string_type string_type;
527 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
528 typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
529
530 re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
531 bool negate = char_set.is_negated();
532 std::memset(result->_map, 0, sizeof(result->_map));
533 //
534 // handle singles first:
535 //
536 item_iterator first, last;
537 set_iterator sfirst, slast;
538 sfirst = char_set.singles_begin();
539 slast = char_set.singles_end();
540 while(sfirst != slast)
541 {
542 for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
543 {
544 if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
545 == this->m_traits.translate(sfirst->first, this->m_icase))
546 result->_map[i] = true;
547 }
548 ++sfirst;
549 }
550 //
551 // OK now handle ranges:
552 //
553 first = char_set.ranges_begin();
554 last = char_set.ranges_end();
555 while(first != last)
556 {
557 // first grab the endpoints of the range:
558 charT c1 = this->m_traits.translate(first->first, this->m_icase);
559 ++first;
560 charT c2 = this->m_traits.translate(first->first, this->m_icase);
561 ++first;
562 // different actions now depending upon whether collation is turned on:
563 if(flags() & regex_constants::collate)
564 {
565 // we need to transform our range into sort keys:
566 charT c3[2] = { c1, charT(0), };
567 string_type s1 = this->m_traits.transform(c3, c3+1);
568 c3[0] = c2;
569 string_type s2 = this->m_traits.transform(c3, c3+1);
570 if(s1 > s2)
571 {
572 // Oops error:
573 return 0;
574 }
575 BOOST_ASSERT(c3[1] == charT(0));
576 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
577 {
578 c3[0] = static_cast<charT>(i);
579 string_type s3 = this->m_traits.transform(c3, c3 +1);
580 if((s1 <= s3) && (s3 <= s2))
581 result->_map[i] = true;
582 }
583 }
584 else
585 {
586 if(char_less(c2, c1))
587 {
588 // Oops error:
589 return 0;
590 }
591 // everything in range matches:
592 std::memset(result->_map + static_cast<unsigned char>(c1), true, 1 + static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1));
593 }
594 }
595 //
596 // and now the classes:
597 //
598 typedef typename traits::char_class_type m_type;
599 m_type m = char_set.classes();
600 if(flags() & regbase::icase)
601 {
602 // adjust m as needed:
603 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
604 m |= m_alpha_mask;
605 }
606 if(m != 0)
607 {
608 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
609 {
610 if(this->m_traits.isctype(static_cast<charT>(i), m))
611 result->_map[i] = true;
612 }
613 }
614 //
615 // and now the negated classes:
616 //
617 m = char_set.negated_classes();
618 if(flags() & regbase::icase)
619 {
620 // adjust m as needed:
621 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
622 m |= m_alpha_mask;
623 }
624 if(m != 0)
625 {
626 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
627 {
628 if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
629 result->_map[i] = true;
630 }
631 }
632 //
633 // now process the equivalence classes:
634 //
635 sfirst = char_set.equivalents_begin();
636 slast = char_set.equivalents_end();
637 while(sfirst != slast)
638 {
639 string_type s;
640 BOOST_ASSERT(static_cast<charT>(0) == sfirst->second);
641 s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
642 if(s.empty())
643 return 0; // invalid or unsupported equivalence class
644 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
645 {
646 charT c[2] = { (static_cast<charT>(i)), charT(0), };
647 string_type s2 = this->m_traits.transform_primary(c, c+1);
648 if(s == s2)
649 result->_map[i] = true;
650 }
651 ++sfirst;
652 }
653 if(negate)
654 {
655 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
656 {
657 result->_map[i] = !(result->_map[i]);
658 }
659 }
660 return result;
661}
662
663template <class charT, class traits>
664void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
665{
666 if(this->m_pdata->m_status)
667 return;
668 // we've added all the states we need, now finish things off.
669 // start by adding a terminating state:
670 append_state(syntax_element_match);
671 // extend storage to store original expression:
672 std::ptrdiff_t len = p2 - p1;
673 m_pdata->m_expression_len = len;
674 charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
675 m_pdata->m_expression = ps;
676 BOOST_REGEX_DETAIL_NS::copy(p1, p2, ps);
677 ps[p2 - p1] = 0;
678 // fill in our other data...
679 // successful parsing implies a zero status:
680 m_pdata->m_status = 0;
681 // get the first state of the machine:
682 m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
683 // fixup pointers in the machine:
684 fixup_pointers(m_pdata->m_first_state);
685 if(m_has_recursions)
686 {
687 m_pdata->m_has_recursions = true;
688 fixup_recursions(m_pdata->m_first_state);
689 if(this->m_pdata->m_status)
690 return;
691 }
692 else
693 m_pdata->m_has_recursions = false;
694 // create nested startmaps:
695 create_startmaps(m_pdata->m_first_state);
696 // create main startmap:
697 std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
698 m_pdata->m_can_be_null = 0;
699
700 m_bad_repeats = 0;
701 if(m_has_recursions)
702 m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
703 create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
704 // get the restart type:
705 m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
706 // optimise a leading repeat if there is one:
707 probe_leading_repeat(m_pdata->m_first_state);
708}
709
710template <class charT, class traits>
711void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
712{
713 while(state)
714 {
715 switch(state->type)
716 {
717 case syntax_element_recurse:
718 m_has_recursions = true;
719 if(state->next.i)
720 state->next.p = getaddress(state->next.i, state);
721 else
722 state->next.p = 0;
723 break;
724 case syntax_element_rep:
725 case syntax_element_dot_rep:
726 case syntax_element_char_rep:
727 case syntax_element_short_set_rep:
728 case syntax_element_long_set_rep:
729 // set the state_id of this repeat:
730 static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
731 BOOST_FALLTHROUGH;
732 case syntax_element_alt:
733 std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
734 static_cast<re_alt*>(state)->can_be_null = 0;
735 BOOST_FALLTHROUGH;
736 case syntax_element_jump:
737 static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
738 BOOST_FALLTHROUGH;
739 default:
740 if(state->next.i)
741 state->next.p = getaddress(state->next.i, state);
742 else
743 state->next.p = 0;
744 }
745 state = state->next.p;
746 }
747}
748
749template <class charT, class traits>
750void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
751{
752 re_syntax_base* base = state;
753 while(state)
754 {
755 switch(state->type)
756 {
757 case syntax_element_assert_backref:
758 {
759 // just check that the index is valid:
760 int idx = static_cast<const re_brace*>(state)->index;
761 if(idx < 0)
762 {
763 idx = -idx-1;
764 if(idx >= 10000)
765 {
766 idx = m_pdata->get_id(idx);
767 if(idx <= 0)
768 {
769 // check of sub-expression that doesn't exist:
770 if(0 == this->m_pdata->m_status) // update the error code if not already set
771 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
772 //
773 // clear the expression, we should be empty:
774 //
775 this->m_pdata->m_expression = 0;
776 this->m_pdata->m_expression_len = 0;
777 //
778 // and throw if required:
779 //
780 if(0 == (this->flags() & regex_constants::no_except))
781 {
782 std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
783 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
784 e.raise();
785 }
786 }
787 }
788 }
789 }
790 break;
791 case syntax_element_recurse:
792 {
793 bool ok = false;
794 re_syntax_base* p = base;
795 std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
796 if(idx > 10000)
797 {
798 //
799 // There may be more than one capture group with this hash, just do what Perl
800 // does and recurse to the leftmost:
801 //
802 idx = m_pdata->get_id(static_cast<int>(idx));
803 }
804 if(idx < 0)
805 {
806 ok = false;
807 }
808 else
809 {
810 while(p)
811 {
812 if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
813 {
814 //
815 // We've found the target of the recursion, set the jump target:
816 //
817 static_cast<re_jump*>(state)->alt.p = p;
818 ok = true;
819 //
820 // Now scan the target for nested repeats:
821 //
822 p = p->next.p;
823 int next_rep_id = 0;
824 while(p)
825 {
826 switch(p->type)
827 {
828 case syntax_element_rep:
829 case syntax_element_dot_rep:
830 case syntax_element_char_rep:
831 case syntax_element_short_set_rep:
832 case syntax_element_long_set_rep:
833 next_rep_id = static_cast<re_repeat*>(p)->state_id;
834 break;
835 case syntax_element_endmark:
836 if(static_cast<const re_brace*>(p)->index == idx)
837 next_rep_id = -1;
838 break;
839 default:
840 break;
841 }
842 if(next_rep_id)
843 break;
844 p = p->next.p;
845 }
846 if(next_rep_id > 0)
847 {
848 static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
849 }
850
851 break;
852 }
853 p = p->next.p;
854 }
855 }
856 if(!ok)
857 {
858 // recursion to sub-expression that doesn't exist:
859 if(0 == this->m_pdata->m_status) // update the error code if not already set
860 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
861 //
862 // clear the expression, we should be empty:
863 //
864 this->m_pdata->m_expression = 0;
865 this->m_pdata->m_expression_len = 0;
866 //
867 // and throw if required:
868 //
869 if(0 == (this->flags() & regex_constants::no_except))
870 {
871 std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
872 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
873 e.raise();
874 }
875 }
876 }
877 break;
878 default:
879 break;
880 }
881 state = state->next.p;
882 }
883}
884
885template <class charT, class traits>
886void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
887{
888 // non-recursive implementation:
889 // create the last map in the machine first, so that earlier maps
890 // can make use of the result...
891 //
892 // This was originally a recursive implementation, but that caused stack
893 // overflows with complex expressions on small stacks (think COM+).
894
895 // start by saving the case setting:
896 bool l_icase = m_icase;
897 std::vector<std::pair<bool, re_syntax_base*> > v;
898
899 while(state)
900 {
901 switch(state->type)
902 {
903 case syntax_element_toggle_case:
904 // we need to track case changes here:
905 m_icase = static_cast<re_case*>(state)->icase;
906 state = state->next.p;
907 continue;
908 case syntax_element_alt:
909 case syntax_element_rep:
910 case syntax_element_dot_rep:
911 case syntax_element_char_rep:
912 case syntax_element_short_set_rep:
913 case syntax_element_long_set_rep:
914 // just push the state onto our stack for now:
915 v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
916 state = state->next.p;
917 break;
918 case syntax_element_backstep:
919 // we need to calculate how big the backstep is:
920 static_cast<re_brace*>(state)->index
921 = this->calculate_backstep(state->next.p);
922 if(static_cast<re_brace*>(state)->index < 0)
923 {
924 // Oops error:
925 if(0 == this->m_pdata->m_status) // update the error code if not already set
926 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
927 //
928 // clear the expression, we should be empty:
929 //
930 this->m_pdata->m_expression = 0;
931 this->m_pdata->m_expression_len = 0;
932 //
933 // and throw if required:
934 //
935 if(0 == (this->flags() & regex_constants::no_except))
936 {
937 std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
938 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
939 e.raise();
940 }
941 }
942 BOOST_FALLTHROUGH;
943 default:
944 state = state->next.p;
945 }
946 }
947
948 // now work through our list, building all the maps as we go:
949 while(v.size())
950 {
951 // Initialize m_recursion_checks if we need it:
952 if(m_has_recursions)
953 m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
954
955 const std::pair<bool, re_syntax_base*>& p = v.back();
956 m_icase = p.first;
957 state = p.second;
958 v.pop_back();
959
960 // Build maps:
961 m_bad_repeats = 0;
962 create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
963 m_bad_repeats = 0;
964
965 if(m_has_recursions)
966 m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
967 create_startmap(static_cast<re_alt*>(state)->alt.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_skip);
968 // adjust the type of the state to allow for faster matching:
969 state->type = this->get_repeat_type(state);
970 }
971 // restore case sensitivity:
972 m_icase = l_icase;
973}
974
975template <class charT, class traits>
976int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
977{
978 typedef typename traits::char_class_type m_type;
979 int result = 0;
980 while(state)
981 {
982 switch(state->type)
983 {
984 case syntax_element_startmark:
985 if((static_cast<re_brace*>(state)->index == -1)
986 || (static_cast<re_brace*>(state)->index == -2))
987 {
988 state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
989 continue;
990 }
991 else if(static_cast<re_brace*>(state)->index == -3)
992 {
993 state = state->next.p->next.p;
994 continue;
995 }
996 break;
997 case syntax_element_endmark:
998 if((static_cast<re_brace*>(state)->index == -1)
999 || (static_cast<re_brace*>(state)->index == -2))
1000 return result;
1001 break;
1002 case syntax_element_literal:
1003 result += static_cast<re_literal*>(state)->length;
1004 break;
1005 case syntax_element_wild:
1006 case syntax_element_set:
1007 result += 1;
1008 break;
1009 case syntax_element_dot_rep:
1010 case syntax_element_char_rep:
1011 case syntax_element_short_set_rep:
1012 case syntax_element_backref:
1013 case syntax_element_rep:
1014 case syntax_element_combining:
1015 case syntax_element_long_set_rep:
1016 case syntax_element_backstep:
1017 {
1018 re_repeat* rep = static_cast<re_repeat *>(state);
1019 // adjust the type of the state to allow for faster matching:
1020 state->type = this->get_repeat_type(state);
1021 if((state->type == syntax_element_dot_rep)
1022 || (state->type == syntax_element_char_rep)
1023 || (state->type == syntax_element_short_set_rep))
1024 {
1025 if(rep->max != rep->min)
1026 return -1;
1027 result += static_cast<int>(rep->min);
1028 state = rep->alt.p;
1029 continue;
1030 }
1031 else if(state->type == syntax_element_long_set_rep)
1032 {
1033 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1034 if(static_cast<re_set_long<m_type>*>(rep->next.p)->singleton == 0)
1035 return -1;
1036 if(rep->max != rep->min)
1037 return -1;
1038 result += static_cast<int>(rep->min);
1039 state = rep->alt.p;
1040 continue;
1041 }
1042 }
1043 return -1;
1044 case syntax_element_long_set:
1045 if(static_cast<re_set_long<m_type>*>(state)->singleton == 0)
1046 return -1;
1047 result += 1;
1048 break;
1049 case syntax_element_jump:
1050 state = static_cast<re_jump*>(state)->alt.p;
1051 continue;
1052 case syntax_element_alt:
1053 {
1054 int r1 = calculate_backstep(state->next.p);
1055 int r2 = calculate_backstep(static_cast<re_alt*>(state)->alt.p);
1056 if((r1 < 0) || (r1 != r2))
1057 return -1;
1058 return result + r1;
1059 }
1060 default:
1061 break;
1062 }
1063 state = state->next.p;
1064 }
1065 return -1;
1066}
1067
1068template <class charT, class traits>
1069void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
1070{
1071 int not_last_jump = 1;
1072 re_syntax_base* recursion_start = 0;
1073 int recursion_sub = 0;
1074 re_syntax_base* recursion_restart = 0;
1075
1076 // track case sensitivity:
1077 bool l_icase = m_icase;
1078
1079 while(state)
1080 {
1081 switch(state->type)
1082 {
1083 case syntax_element_toggle_case:
1084 l_icase = static_cast<re_case*>(state)->icase;
1085 state = state->next.p;
1086 break;
1087 case syntax_element_literal:
1088 {
1089 // don't set anything in *pnull, set each element in l_map
1090 // that could match the first character in the literal:
1091 if(l_map)
1092 {
1093 l_map[0] |= mask_init;
1094 charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
1095 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1096 {
1097 if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
1098 l_map[i] |= mask;
1099 }
1100 }
1101 return;
1102 }
1103 case syntax_element_end_line:
1104 {
1105 // next character must be a line separator (if there is one):
1106 if(l_map)
1107 {
1108 l_map[0] |= mask_init;
1109 l_map[static_cast<unsigned>('\n')] |= mask;
1110 l_map[static_cast<unsigned>('\r')] |= mask;
1111 l_map[static_cast<unsigned>('\f')] |= mask;
1112 l_map[0x85] |= mask;
1113 }
1114 // now figure out if we can match a NULL string at this point:
1115 if(pnull)
1116 create_startmap(state->next.p, 0, pnull, mask);
1117 return;
1118 }
1119 case syntax_element_recurse:
1120 {
1121 BOOST_ASSERT(static_cast<const re_jump*>(state)->alt.p->type == syntax_element_startmark);
1122 recursion_sub = static_cast<re_brace*>(static_cast<const re_jump*>(state)->alt.p)->index;
1123 if(m_recursion_checks[recursion_sub] & 1u)
1124 {
1125 // Infinite recursion!!
1126 if(0 == this->m_pdata->m_status) // update the error code if not already set
1127 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
1128 //
1129 // clear the expression, we should be empty:
1130 //
1131 this->m_pdata->m_expression = 0;
1132 this->m_pdata->m_expression_len = 0;
1133 //
1134 // and throw if required:
1135 //
1136 if(0 == (this->flags() & regex_constants::no_except))
1137 {
1138 std::string message = "Encountered an infinite recursion.";
1139 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
1140 e.raise();
1141 }
1142 }
1143 else if(recursion_start == 0)
1144 {
1145 recursion_start = state;
1146 recursion_restart = state->next.p;
1147 state = static_cast<re_jump*>(state)->alt.p;
1148 m_recursion_checks[recursion_sub] |= 1u;
1149 break;
1150 }
1151 m_recursion_checks[recursion_sub] |= 1u;
1152 // can't handle nested recursion here...
1153 BOOST_FALLTHROUGH;
1154 }
1155 case syntax_element_backref:
1156 // can be null, and any character can match:
1157 if(pnull)
1158 *pnull |= mask;
1159 BOOST_FALLTHROUGH;
1160 case syntax_element_wild:
1161 {
1162 // can't be null, any character can match:
1163 set_all_masks(l_map, mask);
1164 return;
1165 }
1166 case syntax_element_accept:
1167 case syntax_element_match:
1168 {
1169 // must be null, any character can match:
1170 set_all_masks(l_map, mask);
1171 if(pnull)
1172 *pnull |= mask;
1173 return;
1174 }
1175 case syntax_element_word_start:
1176 {
1177 // recurse, then AND with all the word characters:
1178 create_startmap(state->next.p, l_map, pnull, mask);
1179 if(l_map)
1180 {
1181 l_map[0] |= mask_init;
1182 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1183 {
1184 if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
1185 l_map[i] &= static_cast<unsigned char>(~mask);
1186 }
1187 }
1188 return;
1189 }
1190 case syntax_element_word_end:
1191 {
1192 // recurse, then AND with all the word characters:
1193 create_startmap(state->next.p, l_map, pnull, mask);
1194 if(l_map)
1195 {
1196 l_map[0] |= mask_init;
1197 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1198 {
1199 if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
1200 l_map[i] &= static_cast<unsigned char>(~mask);
1201 }
1202 }
1203 return;
1204 }
1205 case syntax_element_buffer_end:
1206 {
1207 // we *must be null* :
1208 if(pnull)
1209 *pnull |= mask;
1210 return;
1211 }
1212 case syntax_element_long_set:
1213 if(l_map)
1214 {
1215 typedef typename traits::char_class_type m_type;
1216 if(static_cast<re_set_long<m_type>*>(state)->singleton)
1217 {
1218 l_map[0] |= mask_init;
1219 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1220 {
1221 charT c = static_cast<charT>(i);
1222 if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<m_type>*>(state), *m_pdata, l_icase))
1223 l_map[i] |= mask;
1224 }
1225 }
1226 else
1227 set_all_masks(l_map, mask);
1228 }
1229 return;
1230 case syntax_element_set:
1231 if(l_map)
1232 {
1233 l_map[0] |= mask_init;
1234 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1235 {
1236 if(static_cast<re_set*>(state)->_map[
1237 static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1238 l_map[i] |= mask;
1239 }
1240 }
1241 return;
1242 case syntax_element_jump:
1243 // take the jump:
1244 state = static_cast<re_alt*>(state)->alt.p;
1245 not_last_jump = -1;
1246 break;
1247 case syntax_element_alt:
1248 case syntax_element_rep:
1249 case syntax_element_dot_rep:
1250 case syntax_element_char_rep:
1251 case syntax_element_short_set_rep:
1252 case syntax_element_long_set_rep:
1253 {
1254 re_alt* rep = static_cast<re_alt*>(state);
1255 if(rep->_map[0] & mask_init)
1256 {
1257 if(l_map)
1258 {
1259 // copy previous results:
1260 l_map[0] |= mask_init;
1261 for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1262 {
1263 if(rep->_map[i] & mask_any)
1264 l_map[i] |= mask;
1265 }
1266 }
1267 if(pnull)
1268 {
1269 if(rep->can_be_null & mask_any)
1270 *pnull |= mask;
1271 }
1272 }
1273 else
1274 {
1275 // we haven't created a startmap for this alternative yet
1276 // so take the union of the two options:
1277 if(is_bad_repeat(state))
1278 {
1279 set_all_masks(l_map, mask);
1280 if(pnull)
1281 *pnull |= mask;
1282 return;
1283 }
1284 set_bad_repeat(state);
1285 create_startmap(state->next.p, l_map, pnull, mask);
1286 if((state->type == syntax_element_alt)
1287 || (static_cast<re_repeat*>(state)->min == 0)
1288 || (not_last_jump == 0))
1289 create_startmap(rep->alt.p, l_map, pnull, mask);
1290 }
1291 }
1292 return;
1293 case syntax_element_soft_buffer_end:
1294 // match newline or null:
1295 if(l_map)
1296 {
1297 l_map[0] |= mask_init;
1298 l_map[static_cast<unsigned>('\n')] |= mask;
1299 l_map[static_cast<unsigned>('\r')] |= mask;
1300 }
1301 if(pnull)
1302 *pnull |= mask;
1303 return;
1304 case syntax_element_endmark:
1305 // need to handle independent subs as a special case:
1306 if(static_cast<re_brace*>(state)->index < 0)
1307 {
1308 // can be null, any character can match:
1309 set_all_masks(l_map, mask);
1310 if(pnull)
1311 *pnull |= mask;
1312 return;
1313 }
1314 else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
1315 {
1316 // recursion termination:
1317 recursion_start = 0;
1318 state = recursion_restart;
1319 break;
1320 }
1321
1322 //
1323 // Normally we just go to the next state... but if this sub-expression is
1324 // the target of a recursion, then we might be ending a recursion, in which
1325 // case we should check whatever follows that recursion, as well as whatever
1326 // follows this state:
1327 //
1328 if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
1329 {
1330 bool ok = false;
1331 re_syntax_base* p = m_pdata->m_first_state;
1332 while(p)
1333 {
1334 if(p->type == syntax_element_recurse)
1335 {
1336 re_brace* p2 = static_cast<re_brace*>(static_cast<re_jump*>(p)->alt.p);
1337 if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
1338 {
1339 ok = true;
1340 break;
1341 }
1342 }
1343 p = p->next.p;
1344 }
1345 if(ok && ((m_recursion_checks[static_cast<re_brace*>(state)->index] & 2u) == 0))
1346 {
1347 m_recursion_checks[static_cast<re_brace*>(state)->index] |= 2u;
1348 create_startmap(p->next.p, l_map, pnull, mask);
1349 }
1350 }
1351 state = state->next.p;
1352 break;
1353
1354 case syntax_element_commit:
1355 set_all_masks(l_map, mask);
1356 // Continue scanning so we can figure out whether we can be null:
1357 state = state->next.p;
1358 break;
1359 case syntax_element_startmark:
1360 // need to handle independent subs as a special case:
1361 if(static_cast<re_brace*>(state)->index == -3)
1362 {
1363 state = state->next.p->next.p;
1364 break;
1365 }
1366 BOOST_FALLTHROUGH;
1367 default:
1368 state = state->next.p;
1369 }
1370 ++not_last_jump;
1371 }
1372}
1373
1374template <class charT, class traits>
1375unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1376{
1377 //
1378 // find out how the machine starts, so we can optimise the search:
1379 //
1380 while(state)
1381 {
1382 switch(state->type)
1383 {
1384 case syntax_element_startmark:
1385 case syntax_element_endmark:
1386 state = state->next.p;
1387 continue;
1388 case syntax_element_start_line:
1389 return regbase::restart_line;
1390 case syntax_element_word_start:
1391 return regbase::restart_word;
1392 case syntax_element_buffer_start:
1393 return regbase::restart_buf;
1394 case syntax_element_restart_continue:
1395 return regbase::restart_continue;
1396 default:
1397 state = 0;
1398 continue;
1399 }
1400 }
1401 return regbase::restart_any;
1402}
1403
1404template <class charT, class traits>
1405void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1406{
1407 //
1408 // set mask in all of bits elements,
1409 // if bits[0] has mask_init not set then we can
1410 // optimise this to a call to memset:
1411 //
1412 if(bits)
1413 {
1414 if(bits[0] == 0)
1415 (std::memset)(bits, mask, 1u << CHAR_BIT);
1416 else
1417 {
1418 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1419 bits[i] |= mask;
1420 }
1421 bits[0] |= mask_init;
1422 }
1423}
1424
1425template <class charT, class traits>
1426bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1427{
1428 switch(pt->type)
1429 {
1430 case syntax_element_rep:
1431 case syntax_element_dot_rep:
1432 case syntax_element_char_rep:
1433 case syntax_element_short_set_rep:
1434 case syntax_element_long_set_rep:
1435 {
1436 unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1437 if(state_id >= sizeof(m_bad_repeats) * CHAR_BIT)
1438 return true; // run out of bits, assume we can't traverse this one.
1439 static const boost::uintmax_t one = 1uL;
1440 return m_bad_repeats & (one << state_id);
1441 }
1442 default:
1443 return false;
1444 }
1445}
1446
1447template <class charT, class traits>
1448void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1449{
1450 switch(pt->type)
1451 {
1452 case syntax_element_rep:
1453 case syntax_element_dot_rep:
1454 case syntax_element_char_rep:
1455 case syntax_element_short_set_rep:
1456 case syntax_element_long_set_rep:
1457 {
1458 unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1459 static const boost::uintmax_t one = 1uL;
1460 if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
1461 m_bad_repeats |= (one << state_id);
1462 }
1463 break;
1464 default:
1465 break;
1466 }
1467}
1468
1469template <class charT, class traits>
1470syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1471{
1472 typedef typename traits::char_class_type m_type;
1473 if(state->type == syntax_element_rep)
1474 {
1475 // check to see if we are repeating a single state:
1476 if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1477 {
1478 switch(state->next.p->type)
1479 {
1480 case BOOST_REGEX_DETAIL_NS::syntax_element_wild:
1481 return BOOST_REGEX_DETAIL_NS::syntax_element_dot_rep;
1482 case BOOST_REGEX_DETAIL_NS::syntax_element_literal:
1483 return BOOST_REGEX_DETAIL_NS::syntax_element_char_rep;
1484 case BOOST_REGEX_DETAIL_NS::syntax_element_set:
1485 return BOOST_REGEX_DETAIL_NS::syntax_element_short_set_rep;
1486 case BOOST_REGEX_DETAIL_NS::syntax_element_long_set:
1487 if(static_cast<BOOST_REGEX_DETAIL_NS::re_set_long<m_type>*>(state->next.p)->singleton)
1488 return BOOST_REGEX_DETAIL_NS::syntax_element_long_set_rep;
1489 break;
1490 default:
1491 break;
1492 }
1493 }
1494 }
1495 return state->type;
1496}
1497
1498template <class charT, class traits>
1499void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1500{
1501 // enumerate our states, and see if we have a leading repeat
1502 // for which failed search restarts can be optimised;
1503 do
1504 {
1505 switch(state->type)
1506 {
1507 case syntax_element_startmark:
1508 if(static_cast<re_brace*>(state)->index >= 0)
1509 {
1510 state = state->next.p;
1511 continue;
1512 }
1513 if((static_cast<re_brace*>(state)->index == -1)
1514 || (static_cast<re_brace*>(state)->index == -2))
1515 {
1516 // skip past the zero width assertion:
1517 state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
1518 continue;
1519 }
1520 if(static_cast<re_brace*>(state)->index == -3)
1521 {
1522 // Have to skip the leading jump state:
1523 state = state->next.p->next.p;
1524 continue;
1525 }
1526 return;
1527 case syntax_element_endmark:
1528 case syntax_element_start_line:
1529 case syntax_element_end_line:
1530 case syntax_element_word_boundary:
1531 case syntax_element_within_word:
1532 case syntax_element_word_start:
1533 case syntax_element_word_end:
1534 case syntax_element_buffer_start:
1535 case syntax_element_buffer_end:
1536 case syntax_element_restart_continue:
1537 state = state->next.p;
1538 break;
1539 case syntax_element_dot_rep:
1540 case syntax_element_char_rep:
1541 case syntax_element_short_set_rep:
1542 case syntax_element_long_set_rep:
1543 if(this->m_has_backrefs == 0)
1544 static_cast<re_repeat*>(state)->leading = true;
1545 BOOST_FALLTHROUGH;
1546 default:
1547 return;
1548 }
1549 }while(state);
1550}
1551
1552
1553} // namespace BOOST_REGEX_DETAIL_NS
1554
1555} // namespace boost
1556
1557#ifdef BOOST_MSVC
1558# pragma warning(pop)
1559#endif
1560
1561#ifdef BOOST_MSVC
1562#pragma warning(push)
1563#pragma warning(disable: 4103)
1564#endif
1565#ifdef BOOST_HAS_ABI_HEADERS
1566# include BOOST_ABI_SUFFIX
1567#endif
1568#ifdef BOOST_MSVC
1569#pragma warning(pop)
1570#endif
1571
1572#endif
1573
1574