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)
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.
20 #ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
21 #define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
23 #include <boost/regex/v4/indexed_bit_flag.hpp>
27 #pragma warning(disable: 4103)
29 #ifdef BOOST_HAS_ABI_HEADERS
30 # include BOOST_ABI_PREFIX
37 # pragma warning(push)
39 #pragma warning(disable:4800)
45 namespace BOOST_REGEX_DETAIL_NS{
47 template <class charT>
48 struct digraph : public std::pair<charT, charT>
50 digraph() : std::pair<charT, charT>(charT(0), charT(0)){}
51 digraph(charT c1) : std::pair<charT, charT>(c1, charT(0)){}
52 digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
54 digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
56 digraph(const Seq& s) : std::pair<charT, charT>()
58 BOOST_ASSERT(s.size() <= 2);
59 BOOST_ASSERT(s.size());
61 this->second = (s.size() > 1) ? s[1] : 0;
65 template <class charT, class traits>
69 typedef digraph<charT> digraph_type;
70 typedef typename traits::string_type string_type;
71 typedef typename traits::char_class_type m_type;
76 m_has_digraphs = false;
78 m_negated_classes = 0;
82 void add_single(const digraph_type& s)
86 m_has_digraphs = true;
89 void add_range(const digraph_type& first, const digraph_type& end)
91 m_ranges.push_back(first);
92 m_ranges.push_back(end);
95 m_has_digraphs = true;
100 m_has_digraphs = true;
105 void add_class(m_type m)
110 void add_negated_class(m_type m)
112 m_negated_classes |= m;
115 void add_equivalent(const digraph_type& s)
117 m_equivalents.insert(s);
120 m_has_digraphs = true;
132 // accessor functions:
134 bool has_digraphs()const
136 return m_has_digraphs;
138 bool is_negated()const
142 typedef typename std::vector<digraph_type>::const_iterator list_iterator;
143 typedef typename std::set<digraph_type>::const_iterator set_iterator;
144 set_iterator singles_begin()const
146 return m_singles.begin();
148 set_iterator singles_end()const
150 return m_singles.end();
152 list_iterator ranges_begin()const
154 return m_ranges.begin();
156 list_iterator ranges_end()const
158 return m_ranges.end();
160 set_iterator equivalents_begin()const
162 return m_equivalents.begin();
164 set_iterator equivalents_end()const
166 return m_equivalents.end();
168 m_type classes()const
172 m_type negated_classes()const
174 return m_negated_classes;
181 std::set<digraph_type> m_singles; // a list of single characters to match
182 std::vector<digraph_type> m_ranges; // a list of end points of our ranges
183 bool m_negate; // true if the set is to be negated
184 bool m_has_digraphs; // true if we have digraphs present
185 m_type m_classes; // character classes to match
186 m_type m_negated_classes; // negated character classes to match
187 bool m_empty; // whether we've added anything yet
188 std::set<digraph_type> m_equivalents; // a list of equivalence classes
191 template <class charT, class traits>
192 class basic_regex_creator
195 basic_regex_creator(regex_data<charT, traits>* data);
196 std::ptrdiff_t getoffset(void* addr)
198 return getoffset(addr, m_pdata->m_data.data());
200 std::ptrdiff_t getoffset(const void* addr, const void* base)
202 return static_cast<const char*>(addr) - static_cast<const char*>(base);
204 re_syntax_base* getaddress(std::ptrdiff_t off)
206 return getaddress(off, m_pdata->m_data.data());
208 re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
210 return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
212 void init(unsigned l_flags)
214 m_pdata->m_flags = l_flags;
215 m_icase = l_flags & regex_constants::icase;
217 regbase::flag_type flags()
219 return m_pdata->m_flags;
221 void flags(regbase::flag_type f)
223 m_pdata->m_flags = f;
224 if(m_icase != static_cast<bool>(f & regbase::icase))
226 m_icase = static_cast<bool>(f & regbase::icase);
229 re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
230 re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
231 re_literal* append_literal(charT c);
232 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
233 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
234 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
235 void finalize(const charT* p1, const charT* p2);
237 regex_data<charT, traits>* m_pdata; // pointer to the basic_regex_data struct we are filling in
238 const ::boost::regex_traits_wrapper<traits>&
239 m_traits; // convenience reference to traits class
240 re_syntax_base* m_last_state; // the last state we added
241 bool m_icase; // true for case insensitive matches
242 unsigned m_repeater_id; // the state_id of the next repeater
243 bool m_has_backrefs; // true if there are actually any backrefs
244 indexed_bit_flag m_backrefs; // bitmask of permitted backrefs
245 boost::uintmax_t m_bad_repeats; // bitmask of repeats we can't deduce a startmap for;
246 bool m_has_recursions; // set when we have recursive expresisons to fixup
247 std::vector<unsigned char> m_recursion_checks; // notes which recursions we've followed while analysing this expression
248 typename traits::char_class_type m_word_mask; // mask used to determine if a character is a word character
249 typename traits::char_class_type m_mask_space; // mask used to determine if a character is a word character
250 typename traits::char_class_type m_lower_mask; // mask used to determine if a character is a lowercase character
251 typename traits::char_class_type m_upper_mask; // mask used to determine if a character is an uppercase character
252 typename traits::char_class_type m_alpha_mask; // mask used to determine if a character is an alphabetic character
254 basic_regex_creator& operator=(const basic_regex_creator&);
255 basic_regex_creator(const basic_regex_creator&);
257 void fixup_pointers(re_syntax_base* state);
258 void fixup_recursions(re_syntax_base* state);
259 void create_startmaps(re_syntax_base* state);
260 int calculate_backstep(re_syntax_base* state);
261 void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
262 unsigned get_restart_type(re_syntax_base* state);
263 void set_all_masks(unsigned char* bits, unsigned char);
264 bool is_bad_repeat(re_syntax_base* pt);
265 void set_bad_repeat(re_syntax_base* pt);
266 syntax_element_type get_repeat_type(re_syntax_base* state);
267 void probe_leading_repeat(re_syntax_base* state);
270 template <class charT, class traits>
271 basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
272 : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_icase(false), m_repeater_id(0),
273 m_has_backrefs(false), m_bad_repeats(0), m_has_recursions(false), m_word_mask(0), m_mask_space(0), m_lower_mask(0), m_upper_mask(0), m_alpha_mask(0)
275 m_pdata->m_data.clear();
276 m_pdata->m_status = ::boost::regex_constants::error_ok;
277 static const charT w = 'w';
278 static const charT s = 's';
279 static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
280 static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
281 static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
282 m_word_mask = m_traits.lookup_classname(&w, &w +1);
283 m_mask_space = m_traits.lookup_classname(&s, &s +1);
284 m_lower_mask = m_traits.lookup_classname(l, l + 5);
285 m_upper_mask = m_traits.lookup_classname(u, u + 5);
286 m_alpha_mask = m_traits.lookup_classname(a, a + 5);
287 m_pdata->m_word_mask = m_word_mask;
288 BOOST_ASSERT(m_word_mask != 0);
289 BOOST_ASSERT(m_mask_space != 0);
290 BOOST_ASSERT(m_lower_mask != 0);
291 BOOST_ASSERT(m_upper_mask != 0);
292 BOOST_ASSERT(m_alpha_mask != 0);
295 template <class charT, class traits>
296 re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
298 // if the state is a backref then make a note of it:
299 if(t == syntax_element_backref)
300 this->m_has_backrefs = true;
301 // append a new state, start by aligning our last one:
302 m_pdata->m_data.align();
303 // set the offset to the next state in our last one:
305 m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
306 // now actually extent our data:
307 m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
308 // fill in boilerplate options in the new state:
309 m_last_state->next.i = 0;
310 m_last_state->type = t;
314 template <class charT, class traits>
315 re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
317 // append a new state, start by aligning our last one:
318 m_pdata->m_data.align();
319 // set the offset to the next state in our last one:
321 m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
322 // remember the last state position:
323 std::ptrdiff_t off = getoffset(m_last_state) + s;
324 // now actually insert our data:
325 re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
326 // fill in boilerplate options in the new state:
327 new_state->next.i = s;
329 m_last_state = getaddress(off);
333 template <class charT, class traits>
334 re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
337 // start by seeing if we have an existing re_literal we can extend:
338 if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
340 // no existing re_literal, create a new one:
341 result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
343 *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
347 // we have an existing re_literal, extend it:
348 std::ptrdiff_t off = getoffset(m_last_state);
349 m_pdata->m_data.extend(sizeof(charT));
350 m_last_state = result = static_cast<re_literal*>(getaddress(off));
351 charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
352 characters[result->length] = m_traits.translate(c, m_icase);
358 template <class charT, class traits>
359 inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
360 const basic_char_set<charT, traits>& char_set)
362 typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
363 return char_set.has_digraphs()
364 ? append_set(char_set, static_cast<mpl::false_*>(0))
365 : append_set(char_set, static_cast<truth_type*>(0));
368 template <class charT, class traits>
369 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
370 const basic_char_set<charT, traits>& char_set, mpl::false_*)
372 typedef typename traits::string_type string_type;
373 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
374 typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
375 typedef typename traits::char_class_type m_type;
377 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>)));
379 // fill in the basics:
381 result->csingles = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.singles_begin(), char_set.singles_end()));
382 result->cranges = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
383 result->cequivalents = static_cast<unsigned int>(::boost::BOOST_REGEX_DETAIL_NS::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
384 result->cclasses = char_set.classes();
385 result->cnclasses = char_set.negated_classes();
386 if(flags() & regbase::icase)
388 // adjust classes as needed:
389 if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
390 result->cclasses |= m_alpha_mask;
391 if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
392 result->cnclasses |= m_alpha_mask;
395 result->isnot = char_set.is_negated();
396 result->singleton = !char_set.has_digraphs();
398 // remember where the state is for later:
400 std::ptrdiff_t offset = getoffset(result);
402 // now extend with all the singles:
404 item_iterator first, last;
405 set_iterator sfirst, slast;
406 sfirst = char_set.singles_begin();
407 slast = char_set.singles_end();
408 while(sfirst != slast)
410 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (sfirst->first == static_cast<charT>(0) ? 1 : sfirst->second ? 3 : 2)));
411 p[0] = m_traits.translate(sfirst->first, m_icase);
412 if(sfirst->first == static_cast<charT>(0))
416 else if(sfirst->second)
418 p[1] = m_traits.translate(sfirst->second, m_icase);
426 // now extend with all the ranges:
428 first = char_set.ranges_begin();
429 last = char_set.ranges_end();
432 // first grab the endpoints of the range:
433 digraph<charT> c1 = *first;
434 c1.first = this->m_traits.translate(c1.first, this->m_icase);
435 c1.second = this->m_traits.translate(c1.second, this->m_icase);
437 digraph<charT> c2 = *first;
438 c2.first = this->m_traits.translate(c2.first, this->m_icase);
439 c2.second = this->m_traits.translate(c2.second, this->m_icase);
442 // different actions now depending upon whether collation is turned on:
443 if(flags() & regex_constants::collate)
445 // we need to transform our range into sort keys:
446 charT a1[3] = { c1.first, c1.second, charT(0), };
447 charT a2[3] = { c2.first, c2.second, charT(0), };
448 s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
449 s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
451 s1 = string_type(1, charT(0));
453 s2 = string_type(1, charT(0));
459 s1.insert(s1.end(), c1.first);
460 s1.insert(s1.end(), c1.second);
463 s1 = string_type(1, c1.first);
466 s2.insert(s2.end(), c2.first);
467 s2.insert(s2.end(), c2.second);
470 s2.insert(s2.end(), c2.first);
477 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
478 BOOST_REGEX_DETAIL_NS::copy(s1.begin(), s1.end(), p);
479 p[s1.size()] = charT(0);
481 BOOST_REGEX_DETAIL_NS::copy(s2.begin(), s2.end(), p);
482 p[s2.size()] = charT(0);
485 // now process the equivalence classes:
487 sfirst = char_set.equivalents_begin();
488 slast = char_set.equivalents_end();
489 while(sfirst != slast)
494 charT cs[3] = { sfirst->first, sfirst->second, charT(0), };
495 s = m_traits.transform_primary(cs, cs+2);
498 s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
500 return 0; // invalid or unsupported equivalence class
501 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
502 BOOST_REGEX_DETAIL_NS::copy(s.begin(), s.end(), p);
503 p[s.size()] = charT(0);
507 // finally reset the address of our last state:
509 m_last_state = result = static_cast<re_set_long<m_type>*>(getaddress(offset));
514 inline bool char_less(T t1, T t2)
518 inline bool char_less(char t1, char t2)
520 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
522 inline bool char_less(signed char t1, signed char t2)
524 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
527 template <class charT, class traits>
528 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
529 const basic_char_set<charT, traits>& char_set, mpl::true_*)
531 typedef typename traits::string_type string_type;
532 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
533 typedef typename basic_char_set<charT, traits>::set_iterator set_iterator;
535 re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
536 bool negate = char_set.is_negated();
537 std::memset(result->_map, 0, sizeof(result->_map));
539 // handle singles first:
541 item_iterator first, last;
542 set_iterator sfirst, slast;
543 sfirst = char_set.singles_begin();
544 slast = char_set.singles_end();
545 while(sfirst != slast)
547 for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
549 if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
550 == this->m_traits.translate(sfirst->first, this->m_icase))
551 result->_map[i] = true;
556 // OK now handle ranges:
558 first = char_set.ranges_begin();
559 last = char_set.ranges_end();
562 // first grab the endpoints of the range:
563 charT c1 = this->m_traits.translate(first->first, this->m_icase);
565 charT c2 = this->m_traits.translate(first->first, this->m_icase);
567 // different actions now depending upon whether collation is turned on:
568 if(flags() & regex_constants::collate)
570 // we need to transform our range into sort keys:
571 charT c3[2] = { c1, charT(0), };
572 string_type s1 = this->m_traits.transform(c3, c3+1);
574 string_type s2 = this->m_traits.transform(c3, c3+1);
580 BOOST_ASSERT(c3[1] == charT(0));
581 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
583 c3[0] = static_cast<charT>(i);
584 string_type s3 = this->m_traits.transform(c3, c3 +1);
585 if((s1 <= s3) && (s3 <= s2))
586 result->_map[i] = true;
591 if(char_less(c2, c1))
596 // everything in range matches:
597 std::memset(result->_map + static_cast<unsigned char>(c1), true, static_cast<unsigned char>(1u) + static_cast<unsigned char>(static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1)));
601 // and now the classes:
603 typedef typename traits::char_class_type m_type;
604 m_type m = char_set.classes();
605 if(flags() & regbase::icase)
607 // adjust m as needed:
608 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
613 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
615 if(this->m_traits.isctype(static_cast<charT>(i), m))
616 result->_map[i] = true;
620 // and now the negated classes:
622 m = char_set.negated_classes();
623 if(flags() & regbase::icase)
625 // adjust m as needed:
626 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
631 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
633 if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
634 result->_map[i] = true;
638 // now process the equivalence classes:
640 sfirst = char_set.equivalents_begin();
641 slast = char_set.equivalents_end();
642 while(sfirst != slast)
645 BOOST_ASSERT(static_cast<charT>(0) == sfirst->second);
646 s = m_traits.transform_primary(&sfirst->first, &sfirst->first+1);
648 return 0; // invalid or unsupported equivalence class
649 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
651 charT c[2] = { (static_cast<charT>(i)), charT(0), };
652 string_type s2 = this->m_traits.transform_primary(c, c+1);
654 result->_map[i] = true;
660 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
662 result->_map[i] = !(result->_map[i]);
668 template <class charT, class traits>
669 void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
671 if(this->m_pdata->m_status)
673 // we've added all the states we need, now finish things off.
674 // start by adding a terminating state:
675 append_state(syntax_element_match);
676 // extend storage to store original expression:
677 std::ptrdiff_t len = p2 - p1;
678 m_pdata->m_expression_len = len;
679 charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
680 m_pdata->m_expression = ps;
681 BOOST_REGEX_DETAIL_NS::copy(p1, p2, ps);
683 // fill in our other data...
684 // successful parsing implies a zero status:
685 m_pdata->m_status = 0;
686 // get the first state of the machine:
687 m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
688 // fixup pointers in the machine:
689 fixup_pointers(m_pdata->m_first_state);
692 m_pdata->m_has_recursions = true;
693 fixup_recursions(m_pdata->m_first_state);
694 if(this->m_pdata->m_status)
698 m_pdata->m_has_recursions = false;
699 // create nested startmaps:
700 create_startmaps(m_pdata->m_first_state);
701 // create main startmap:
702 std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
703 m_pdata->m_can_be_null = 0;
707 m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
708 create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
709 // get the restart type:
710 m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
711 // optimise a leading repeat if there is one:
712 probe_leading_repeat(m_pdata->m_first_state);
715 template <class charT, class traits>
716 void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
722 case syntax_element_recurse:
723 m_has_recursions = true;
725 state->next.p = getaddress(state->next.i, state);
729 case syntax_element_rep:
730 case syntax_element_dot_rep:
731 case syntax_element_char_rep:
732 case syntax_element_short_set_rep:
733 case syntax_element_long_set_rep:
734 // set the state_id of this repeat:
735 static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
737 case syntax_element_alt:
738 std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
739 static_cast<re_alt*>(state)->can_be_null = 0;
741 case syntax_element_jump:
742 static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
746 state->next.p = getaddress(state->next.i, state);
750 state = state->next.p;
754 template <class charT, class traits>
755 void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
757 re_syntax_base* base = state;
762 case syntax_element_assert_backref:
764 // just check that the index is valid:
765 int idx = static_cast<const re_brace*>(state)->index;
769 if(idx >= hash_value_mask)
771 idx = m_pdata->get_id(idx);
774 // check of sub-expression that doesn't exist:
775 if(0 == this->m_pdata->m_status) // update the error code if not already set
776 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
778 // clear the expression, we should be empty:
780 this->m_pdata->m_expression = 0;
781 this->m_pdata->m_expression_len = 0;
783 // and throw if required:
785 if(0 == (this->flags() & regex_constants::no_except))
787 std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
788 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
796 case syntax_element_recurse:
799 re_syntax_base* p = base;
800 std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
801 if(idx >= hash_value_mask)
804 // There may be more than one capture group with this hash, just do what Perl
805 // does and recurse to the leftmost:
807 idx = m_pdata->get_id(static_cast<int>(idx));
817 if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
820 // We've found the target of the recursion, set the jump target:
822 static_cast<re_jump*>(state)->alt.p = p;
825 // Now scan the target for nested repeats:
833 case syntax_element_rep:
834 case syntax_element_dot_rep:
835 case syntax_element_char_rep:
836 case syntax_element_short_set_rep:
837 case syntax_element_long_set_rep:
838 next_rep_id = static_cast<re_repeat*>(p)->state_id;
840 case syntax_element_endmark:
841 if(static_cast<const re_brace*>(p)->index == idx)
853 static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
863 // recursion to sub-expression that doesn't exist:
864 if(0 == this->m_pdata->m_status) // update the error code if not already set
865 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
867 // clear the expression, we should be empty:
869 this->m_pdata->m_expression = 0;
870 this->m_pdata->m_expression_len = 0;
872 // and throw if required:
874 if(0 == (this->flags() & regex_constants::no_except))
876 std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
877 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
886 state = state->next.p;
890 template <class charT, class traits>
891 void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
893 // non-recursive implementation:
894 // create the last map in the machine first, so that earlier maps
895 // can make use of the result...
897 // This was originally a recursive implementation, but that caused stack
898 // overflows with complex expressions on small stacks (think COM+).
900 // start by saving the case setting:
901 bool l_icase = m_icase;
902 std::vector<std::pair<bool, re_syntax_base*> > v;
908 case syntax_element_toggle_case:
909 // we need to track case changes here:
910 m_icase = static_cast<re_case*>(state)->icase;
911 state = state->next.p;
913 case syntax_element_alt:
914 case syntax_element_rep:
915 case syntax_element_dot_rep:
916 case syntax_element_char_rep:
917 case syntax_element_short_set_rep:
918 case syntax_element_long_set_rep:
919 // just push the state onto our stack for now:
920 v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
921 state = state->next.p;
923 case syntax_element_backstep:
924 // we need to calculate how big the backstep is:
925 static_cast<re_brace*>(state)->index
926 = this->calculate_backstep(state->next.p);
927 if(static_cast<re_brace*>(state)->index < 0)
930 if(0 == this->m_pdata->m_status) // update the error code if not already set
931 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
933 // clear the expression, we should be empty:
935 this->m_pdata->m_expression = 0;
936 this->m_pdata->m_expression_len = 0;
938 // and throw if required:
940 if(0 == (this->flags() & regex_constants::no_except))
942 std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
943 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
949 state = state->next.p;
953 // now work through our list, building all the maps as we go:
956 // Initialize m_recursion_checks if we need it:
958 m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
960 const std::pair<bool, re_syntax_base*>& p = v.back();
967 create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
971 m_recursion_checks.assign(1 + m_pdata->m_mark_count, 0u);
972 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);
973 // adjust the type of the state to allow for faster matching:
974 state->type = this->get_repeat_type(state);
976 // restore case sensitivity:
980 template <class charT, class traits>
981 int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
983 typedef typename traits::char_class_type m_type;
989 case syntax_element_startmark:
990 if((static_cast<re_brace*>(state)->index == -1)
991 || (static_cast<re_brace*>(state)->index == -2))
993 state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
996 else if(static_cast<re_brace*>(state)->index == -3)
998 state = state->next.p->next.p;
1002 case syntax_element_endmark:
1003 if((static_cast<re_brace*>(state)->index == -1)
1004 || (static_cast<re_brace*>(state)->index == -2))
1007 case syntax_element_literal:
1008 result += static_cast<re_literal*>(state)->length;
1010 case syntax_element_wild:
1011 case syntax_element_set:
1014 case syntax_element_dot_rep:
1015 case syntax_element_char_rep:
1016 case syntax_element_short_set_rep:
1017 case syntax_element_backref:
1018 case syntax_element_rep:
1019 case syntax_element_combining:
1020 case syntax_element_long_set_rep:
1021 case syntax_element_backstep:
1023 re_repeat* rep = static_cast<re_repeat *>(state);
1024 // adjust the type of the state to allow for faster matching:
1025 state->type = this->get_repeat_type(state);
1026 if((state->type == syntax_element_dot_rep)
1027 || (state->type == syntax_element_char_rep)
1028 || (state->type == syntax_element_short_set_rep))
1030 if(rep->max != rep->min)
1032 result += static_cast<int>(rep->min);
1036 else if(state->type == syntax_element_long_set_rep)
1038 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1039 if(static_cast<re_set_long<m_type>*>(rep->next.p)->singleton == 0)
1041 if(rep->max != rep->min)
1043 result += static_cast<int>(rep->min);
1049 case syntax_element_long_set:
1050 if(static_cast<re_set_long<m_type>*>(state)->singleton == 0)
1054 case syntax_element_jump:
1055 state = static_cast<re_jump*>(state)->alt.p;
1057 case syntax_element_alt:
1059 int r1 = calculate_backstep(state->next.p);
1060 int r2 = calculate_backstep(static_cast<re_alt*>(state)->alt.p);
1061 if((r1 < 0) || (r1 != r2))
1068 state = state->next.p;
1073 struct recursion_saver
1075 std::vector<unsigned char> saved_state;
1076 std::vector<unsigned char>* state;
1077 recursion_saver(std::vector<unsigned char>* p) : saved_state(*p), state(p) {}
1080 state->swap(saved_state);
1084 template <class charT, class traits>
1085 void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
1087 recursion_saver saved_recursions(&m_recursion_checks);
1088 int not_last_jump = 1;
1089 re_syntax_base* recursion_start = 0;
1090 int recursion_sub = 0;
1091 re_syntax_base* recursion_restart = 0;
1093 // track case sensitivity:
1094 bool l_icase = m_icase;
1100 case syntax_element_toggle_case:
1101 l_icase = static_cast<re_case*>(state)->icase;
1102 state = state->next.p;
1104 case syntax_element_literal:
1106 // don't set anything in *pnull, set each element in l_map
1107 // that could match the first character in the literal:
1110 l_map[0] |= mask_init;
1111 charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
1112 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1114 if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
1120 case syntax_element_end_line:
1122 // next character must be a line separator (if there is one):
1125 l_map[0] |= mask_init;
1126 l_map[static_cast<unsigned>('\n')] |= mask;
1127 l_map[static_cast<unsigned>('\r')] |= mask;
1128 l_map[static_cast<unsigned>('\f')] |= mask;
1129 l_map[0x85] |= mask;
1131 // now figure out if we can match a NULL string at this point:
1133 create_startmap(state->next.p, 0, pnull, mask);
1136 case syntax_element_recurse:
1138 BOOST_ASSERT(static_cast<const re_jump*>(state)->alt.p->type == syntax_element_startmark);
1139 recursion_sub = static_cast<re_brace*>(static_cast<const re_jump*>(state)->alt.p)->index;
1140 if(m_recursion_checks[recursion_sub] & 1u)
1142 // Infinite recursion!!
1143 if(0 == this->m_pdata->m_status) // update the error code if not already set
1144 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
1146 // clear the expression, we should be empty:
1148 this->m_pdata->m_expression = 0;
1149 this->m_pdata->m_expression_len = 0;
1151 // and throw if required:
1153 if(0 == (this->flags() & regex_constants::no_except))
1155 std::string message = "Encountered an infinite recursion.";
1156 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
1160 else if(recursion_start == 0)
1162 recursion_start = state;
1163 recursion_restart = state->next.p;
1164 state = static_cast<re_jump*>(state)->alt.p;
1165 m_recursion_checks[recursion_sub] |= 1u;
1168 m_recursion_checks[recursion_sub] |= 1u;
1169 // can't handle nested recursion here...
1172 case syntax_element_backref:
1173 // can be null, and any character can match:
1177 case syntax_element_wild:
1179 // can't be null, any character can match:
1180 set_all_masks(l_map, mask);
1183 case syntax_element_accept:
1184 case syntax_element_match:
1186 // must be null, any character can match:
1187 set_all_masks(l_map, mask);
1192 case syntax_element_word_start:
1194 // recurse, then AND with all the word characters:
1195 create_startmap(state->next.p, l_map, pnull, mask);
1198 l_map[0] |= mask_init;
1199 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1201 if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
1202 l_map[i] &= static_cast<unsigned char>(~mask);
1207 case syntax_element_word_end:
1209 // recurse, then AND with all the word characters:
1210 create_startmap(state->next.p, l_map, pnull, mask);
1213 l_map[0] |= mask_init;
1214 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1216 if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
1217 l_map[i] &= static_cast<unsigned char>(~mask);
1222 case syntax_element_buffer_end:
1224 // we *must be null* :
1229 case syntax_element_long_set:
1232 typedef typename traits::char_class_type m_type;
1233 if(static_cast<re_set_long<m_type>*>(state)->singleton)
1235 l_map[0] |= mask_init;
1236 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1238 charT c = static_cast<charT>(i);
1239 if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<m_type>*>(state), *m_pdata, l_icase))
1244 set_all_masks(l_map, mask);
1247 case syntax_element_set:
1250 l_map[0] |= mask_init;
1251 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1253 if(static_cast<re_set*>(state)->_map[
1254 static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1259 case syntax_element_jump:
1261 state = static_cast<re_alt*>(state)->alt.p;
1264 case syntax_element_alt:
1265 case syntax_element_rep:
1266 case syntax_element_dot_rep:
1267 case syntax_element_char_rep:
1268 case syntax_element_short_set_rep:
1269 case syntax_element_long_set_rep:
1271 re_alt* rep = static_cast<re_alt*>(state);
1272 if(rep->_map[0] & mask_init)
1276 // copy previous results:
1277 l_map[0] |= mask_init;
1278 for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1280 if(rep->_map[i] & mask_any)
1286 if(rep->can_be_null & mask_any)
1292 // we haven't created a startmap for this alternative yet
1293 // so take the union of the two options:
1294 if(is_bad_repeat(state))
1296 set_all_masks(l_map, mask);
1301 set_bad_repeat(state);
1302 create_startmap(state->next.p, l_map, pnull, mask);
1303 if((state->type == syntax_element_alt)
1304 || (static_cast<re_repeat*>(state)->min == 0)
1305 || (not_last_jump == 0))
1306 create_startmap(rep->alt.p, l_map, pnull, mask);
1310 case syntax_element_soft_buffer_end:
1311 // match newline or null:
1314 l_map[0] |= mask_init;
1315 l_map[static_cast<unsigned>('\n')] |= mask;
1316 l_map[static_cast<unsigned>('\r')] |= mask;
1321 case syntax_element_endmark:
1322 // need to handle independent subs as a special case:
1323 if(static_cast<re_brace*>(state)->index < 0)
1325 // can be null, any character can match:
1326 set_all_masks(l_map, mask);
1331 else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
1333 // recursion termination:
1334 recursion_start = 0;
1335 state = recursion_restart;
1340 // Normally we just go to the next state... but if this sub-expression is
1341 // the target of a recursion, then we might be ending a recursion, in which
1342 // case we should check whatever follows that recursion, as well as whatever
1343 // follows this state:
1345 if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
1348 re_syntax_base* p = m_pdata->m_first_state;
1351 if(p->type == syntax_element_recurse)
1353 re_brace* p2 = static_cast<re_brace*>(static_cast<re_jump*>(p)->alt.p);
1354 if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
1362 if(ok && ((m_recursion_checks[static_cast<re_brace*>(state)->index] & 2u) == 0))
1364 m_recursion_checks[static_cast<re_brace*>(state)->index] |= 2u;
1365 create_startmap(p->next.p, l_map, pnull, mask);
1368 state = state->next.p;
1371 case syntax_element_commit:
1372 set_all_masks(l_map, mask);
1373 // Continue scanning so we can figure out whether we can be null:
1374 state = state->next.p;
1376 case syntax_element_startmark:
1377 // need to handle independent subs as a special case:
1378 if(static_cast<re_brace*>(state)->index == -3)
1380 state = state->next.p->next.p;
1385 state = state->next.p;
1391 template <class charT, class traits>
1392 unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1395 // find out how the machine starts, so we can optimise the search:
1401 case syntax_element_startmark:
1402 case syntax_element_endmark:
1403 state = state->next.p;
1405 case syntax_element_start_line:
1406 return regbase::restart_line;
1407 case syntax_element_word_start:
1408 return regbase::restart_word;
1409 case syntax_element_buffer_start:
1410 return regbase::restart_buf;
1411 case syntax_element_restart_continue:
1412 return regbase::restart_continue;
1418 return regbase::restart_any;
1421 template <class charT, class traits>
1422 void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1425 // set mask in all of bits elements,
1426 // if bits[0] has mask_init not set then we can
1427 // optimise this to a call to memset:
1432 (std::memset)(bits, mask, 1u << CHAR_BIT);
1435 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1438 bits[0] |= mask_init;
1442 template <class charT, class traits>
1443 bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1447 case syntax_element_rep:
1448 case syntax_element_dot_rep:
1449 case syntax_element_char_rep:
1450 case syntax_element_short_set_rep:
1451 case syntax_element_long_set_rep:
1453 unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1454 if(state_id >= sizeof(m_bad_repeats) * CHAR_BIT)
1455 return true; // run out of bits, assume we can't traverse this one.
1456 static const boost::uintmax_t one = 1uL;
1457 return m_bad_repeats & (one << state_id);
1464 template <class charT, class traits>
1465 void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1469 case syntax_element_rep:
1470 case syntax_element_dot_rep:
1471 case syntax_element_char_rep:
1472 case syntax_element_short_set_rep:
1473 case syntax_element_long_set_rep:
1475 unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1476 static const boost::uintmax_t one = 1uL;
1477 if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
1478 m_bad_repeats |= (one << state_id);
1486 template <class charT, class traits>
1487 syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1489 typedef typename traits::char_class_type m_type;
1490 if(state->type == syntax_element_rep)
1492 // check to see if we are repeating a single state:
1493 if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1495 switch(state->next.p->type)
1497 case BOOST_REGEX_DETAIL_NS::syntax_element_wild:
1498 return BOOST_REGEX_DETAIL_NS::syntax_element_dot_rep;
1499 case BOOST_REGEX_DETAIL_NS::syntax_element_literal:
1500 return BOOST_REGEX_DETAIL_NS::syntax_element_char_rep;
1501 case BOOST_REGEX_DETAIL_NS::syntax_element_set:
1502 return BOOST_REGEX_DETAIL_NS::syntax_element_short_set_rep;
1503 case BOOST_REGEX_DETAIL_NS::syntax_element_long_set:
1504 if(static_cast<BOOST_REGEX_DETAIL_NS::re_set_long<m_type>*>(state->next.p)->singleton)
1505 return BOOST_REGEX_DETAIL_NS::syntax_element_long_set_rep;
1515 template <class charT, class traits>
1516 void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1518 // enumerate our states, and see if we have a leading repeat
1519 // for which failed search restarts can be optimised;
1524 case syntax_element_startmark:
1525 if(static_cast<re_brace*>(state)->index >= 0)
1527 state = state->next.p;
1531 # pragma warning(push)
1532 #pragma warning(disable:6011)
1534 if((static_cast<re_brace*>(state)->index == -1)
1535 || (static_cast<re_brace*>(state)->index == -2))
1537 // skip past the zero width assertion:
1538 state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
1542 # pragma warning(pop)
1544 if(static_cast<re_brace*>(state)->index == -3)
1546 // Have to skip the leading jump state:
1547 state = state->next.p->next.p;
1551 case syntax_element_endmark:
1552 case syntax_element_start_line:
1553 case syntax_element_end_line:
1554 case syntax_element_word_boundary:
1555 case syntax_element_within_word:
1556 case syntax_element_word_start:
1557 case syntax_element_word_end:
1558 case syntax_element_buffer_start:
1559 case syntax_element_buffer_end:
1560 case syntax_element_restart_continue:
1561 state = state->next.p;
1563 case syntax_element_dot_rep:
1564 case syntax_element_char_rep:
1565 case syntax_element_short_set_rep:
1566 case syntax_element_long_set_rep:
1567 if(this->m_has_backrefs == 0)
1568 static_cast<re_repeat*>(state)->leading = true;
1577 } // namespace BOOST_REGEX_DETAIL_NS
1579 } // namespace boost
1582 # pragma warning(pop)
1586 #pragma warning(push)
1587 #pragma warning(disable: 4103)
1589 #ifdef BOOST_HAS_ABI_HEADERS
1590 # include BOOST_ABI_SUFFIX
1593 #pragma warning(pop)