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
25 #pragma warning(disable: 4103)
27 #ifdef BOOST_HAS_ABI_HEADERS
28 # include BOOST_ABI_PREFIX
35 # pragma warning(push)
36 # pragma warning(disable: 4800)
43 template <class charT>
44 struct digraph : public std::pair<charT, charT>
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)
50 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
51 digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
54 digraph(const Seq& s) : std::pair<charT, charT>()
56 BOOST_ASSERT(s.size() <= 2);
57 BOOST_ASSERT(s.size());
59 this->second = (s.size() > 1) ? s[1] : 0;
63 template <class charT, class traits>
67 typedef digraph<charT> digraph_type;
68 typedef typename traits::string_type string_type;
69 typedef typename traits::char_class_type mask_type;
74 m_has_digraphs = false;
76 m_negated_classes = 0;
80 void add_single(const digraph_type& s)
82 m_singles.insert(m_singles.end(), s);
84 m_has_digraphs = true;
87 void add_range(const digraph_type& first, const digraph_type& end)
89 m_ranges.insert(m_ranges.end(), first);
90 m_ranges.insert(m_ranges.end(), end);
93 m_has_digraphs = true;
98 m_has_digraphs = true;
103 void add_class(mask_type m)
108 void add_negated_class(mask_type m)
110 m_negated_classes |= m;
113 void add_equivalent(const digraph_type& s)
115 m_equivalents.insert(m_equivalents.end(), s);
118 m_has_digraphs = true;
130 // accessor functions:
132 bool has_digraphs()const
134 return m_has_digraphs;
136 bool is_negated()const
140 typedef typename std::vector<digraph_type>::const_iterator list_iterator;
141 list_iterator singles_begin()const
143 return m_singles.begin();
145 list_iterator singles_end()const
147 return m_singles.end();
149 list_iterator ranges_begin()const
151 return m_ranges.begin();
153 list_iterator ranges_end()const
155 return m_ranges.end();
157 list_iterator equivalents_begin()const
159 return m_equivalents.begin();
161 list_iterator equivalents_end()const
163 return m_equivalents.end();
165 mask_type classes()const
169 mask_type negated_classes()const
171 return m_negated_classes;
178 std::vector<digraph_type> m_singles; // a list of single characters to match
179 std::vector<digraph_type> m_ranges; // a list of end points of our ranges
180 bool m_negate; // true if the set is to be negated
181 bool m_has_digraphs; // true if we have digraphs present
182 mask_type m_classes; // character classes to match
183 mask_type m_negated_classes; // negated character classes to match
184 bool m_empty; // whether we've added anything yet
185 std::vector<digraph_type> m_equivalents; // a list of equivalence classes
188 template <class charT, class traits>
189 class basic_regex_creator
192 basic_regex_creator(regex_data<charT, traits>* data);
193 std::ptrdiff_t getoffset(void* addr)
195 return getoffset(addr, m_pdata->m_data.data());
197 std::ptrdiff_t getoffset(const void* addr, const void* base)
199 return static_cast<const char*>(addr) - static_cast<const char*>(base);
201 re_syntax_base* getaddress(std::ptrdiff_t off)
203 return getaddress(off, m_pdata->m_data.data());
205 re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
207 return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
209 void init(unsigned l_flags)
211 m_pdata->m_flags = l_flags;
212 m_icase = l_flags & regex_constants::icase;
214 regbase::flag_type flags()
216 return m_pdata->m_flags;
218 void flags(regbase::flag_type f)
220 m_pdata->m_flags = f;
221 if(m_icase != static_cast<bool>(f & regbase::icase))
223 m_icase = static_cast<bool>(f & regbase::icase);
226 re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
227 re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
228 re_literal* append_literal(charT c);
229 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
230 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
231 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
232 void finalize(const charT* p1, const charT* p2);
234 regex_data<charT, traits>* m_pdata; // pointer to the basic_regex_data struct we are filling in
235 const ::boost::regex_traits_wrapper<traits>&
236 m_traits; // convenience reference to traits class
237 re_syntax_base* m_last_state; // the last state we added
238 bool m_icase; // true for case insensitive matches
239 unsigned m_repeater_id; // the state_id of the next repeater
240 bool m_has_backrefs; // true if there are actually any backrefs
241 unsigned m_backrefs; // bitmask of permitted backrefs
242 boost::uintmax_t m_bad_repeats; // bitmask of repeats we can't deduce a startmap for;
243 bool m_has_recursions; // set when we have recursive expresisons to fixup
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
250 basic_regex_creator& operator=(const basic_regex_creator&);
251 basic_regex_creator(const basic_regex_creator&);
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);
266 template <class charT, class traits>
267 basic_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)
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);
290 template <class charT, class traits>
291 re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
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:
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;
309 template <class charT, class traits>
310 re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
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:
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;
324 m_last_state = getaddress(off);
328 template <class charT, class traits>
329 re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
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))
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)));
338 *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
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);
353 template <class charT, class traits>
354 inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
355 const basic_char_set<charT, traits>& char_set)
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));
363 template <class charT, class traits>
364 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
365 const basic_char_set<charT, traits>& char_set, mpl::false_*)
367 typedef typename traits::string_type string_type;
368 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
369 typedef typename traits::char_class_type mask_type;
371 re_set_long<mask_type>* result = static_cast<re_set_long<mask_type>*>(append_state(syntax_element_long_set, sizeof(re_set_long<mask_type>)));
373 // fill in the basics:
375 result->csingles = static_cast<unsigned int>(::boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end()));
376 result->cranges = static_cast<unsigned int>(::boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
377 result->cequivalents = static_cast<unsigned int>(::boost::re_detail::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
378 result->cclasses = char_set.classes();
379 result->cnclasses = char_set.negated_classes();
380 if(flags() & regbase::icase)
382 // adjust classes as needed:
383 if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
384 result->cclasses |= m_alpha_mask;
385 if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
386 result->cnclasses |= m_alpha_mask;
389 result->isnot = char_set.is_negated();
390 result->singleton = !char_set.has_digraphs();
392 // remember where the state is for later:
394 std::ptrdiff_t offset = getoffset(result);
396 // now extend with all the singles:
398 item_iterator first, last;
399 first = char_set.singles_begin();
400 last = char_set.singles_end();
403 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (first->second ? 3 : 2)));
404 p[0] = m_traits.translate(first->first, m_icase);
407 p[1] = m_traits.translate(first->second, m_icase);
415 // now extend with all the ranges:
417 first = char_set.ranges_begin();
418 last = char_set.ranges_end();
421 // first grab the endpoints of the range:
422 digraph<charT> c1 = *first;
423 c1.first = this->m_traits.translate(c1.first, this->m_icase);
424 c1.second = this->m_traits.translate(c1.second, this->m_icase);
426 digraph<charT> c2 = *first;
427 c2.first = this->m_traits.translate(c2.first, this->m_icase);
428 c2.second = this->m_traits.translate(c2.second, this->m_icase);
431 // different actions now depending upon whether collation is turned on:
432 if(flags() & regex_constants::collate)
434 // we need to transform our range into sort keys:
435 #if BOOST_WORKAROUND(__GNUC__, < 3)
436 string_type in(3, charT(0));
439 s1 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
442 s2 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
444 charT a1[3] = { c1.first, c1.second, charT(0), };
445 charT a2[3] = { c2.first, c2.second, charT(0), };
446 s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
447 s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
450 s1 = string_type(1, charT(0));
452 s2 = string_type(1, charT(0));
458 s1.insert(s1.end(), c1.first);
459 s1.insert(s1.end(), c1.second);
462 s1 = string_type(1, c1.first);
465 s2.insert(s2.end(), c2.first);
466 s2.insert(s2.end(), c2.second);
469 s2.insert(s2.end(), c2.first);
476 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
477 re_detail::copy(s1.begin(), s1.end(), p);
478 p[s1.size()] = charT(0);
480 re_detail::copy(s2.begin(), s2.end(), p);
481 p[s2.size()] = charT(0);
484 // now process the equivalence classes:
486 first = char_set.equivalents_begin();
487 last = char_set.equivalents_end();
493 #if BOOST_WORKAROUND(__GNUC__, < 3)
494 string_type in(3, charT(0));
495 in[0] = first->first;
496 in[1] = first->second;
497 s = m_traits.transform_primary(in.c_str(), in.c_str()+2);
499 charT cs[3] = { first->first, first->second, charT(0), };
500 s = m_traits.transform_primary(cs, cs+2);
504 s = m_traits.transform_primary(&first->first, &first->first+1);
506 return 0; // invalid or unsupported equivalence class
507 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
508 re_detail::copy(s.begin(), s.end(), p);
509 p[s.size()] = charT(0);
513 // finally reset the address of our last state:
515 m_last_state = result = static_cast<re_set_long<mask_type>*>(getaddress(offset));
522 inline bool char_less(T t1, T t2)
527 inline bool char_less<char>(char t1, char t2)
529 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
532 inline bool char_less<signed char>(signed char t1, signed char t2)
534 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
538 template <class charT, class traits>
539 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
540 const basic_char_set<charT, traits>& char_set, mpl::true_*)
542 typedef typename traits::string_type string_type;
543 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
545 re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
546 bool negate = char_set.is_negated();
547 std::memset(result->_map, 0, sizeof(result->_map));
549 // handle singles first:
551 item_iterator first, last;
552 first = char_set.singles_begin();
553 last = char_set.singles_end();
556 for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
558 if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
559 == this->m_traits.translate(first->first, this->m_icase))
560 result->_map[i] = true;
565 // OK now handle ranges:
567 first = char_set.ranges_begin();
568 last = char_set.ranges_end();
571 // first grab the endpoints of the range:
572 charT c1 = this->m_traits.translate(first->first, this->m_icase);
574 charT c2 = this->m_traits.translate(first->first, this->m_icase);
576 // different actions now depending upon whether collation is turned on:
577 if(flags() & regex_constants::collate)
579 // we need to transform our range into sort keys:
580 charT c3[2] = { c1, charT(0), };
581 string_type s1 = this->m_traits.transform(c3, c3+1);
583 string_type s2 = this->m_traits.transform(c3, c3+1);
589 BOOST_ASSERT(c3[1] == charT(0));
590 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
592 c3[0] = static_cast<charT>(i);
593 string_type s3 = this->m_traits.transform(c3, c3 +1);
594 if((s1 <= s3) && (s3 <= s2))
595 result->_map[i] = true;
600 if(char_less<charT>(c2, c1))
605 // everything in range matches:
606 std::memset(result->_map + static_cast<unsigned char>(c1), true, 1 + static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1));
610 // and now the classes:
612 typedef typename traits::char_class_type mask_type;
613 mask_type m = char_set.classes();
614 if(flags() & regbase::icase)
616 // adjust m as needed:
617 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
622 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
624 if(this->m_traits.isctype(static_cast<charT>(i), m))
625 result->_map[i] = true;
629 // and now the negated classes:
631 m = char_set.negated_classes();
632 if(flags() & regbase::icase)
634 // adjust m as needed:
635 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
640 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
642 if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
643 result->_map[i] = true;
647 // now process the equivalence classes:
649 first = char_set.equivalents_begin();
650 last = char_set.equivalents_end();
654 BOOST_ASSERT(static_cast<charT>(0) == first->second);
655 s = m_traits.transform_primary(&first->first, &first->first+1);
657 return 0; // invalid or unsupported equivalence class
658 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
660 charT c[2] = { (static_cast<charT>(i)), charT(0), };
661 string_type s2 = this->m_traits.transform_primary(c, c+1);
663 result->_map[i] = true;
669 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
671 result->_map[i] = !(result->_map[i]);
677 template <class charT, class traits>
678 void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
680 if(this->m_pdata->m_status)
682 // we've added all the states we need, now finish things off.
683 // start by adding a terminating state:
684 append_state(syntax_element_match);
685 // extend storage to store original expression:
686 std::ptrdiff_t len = p2 - p1;
687 m_pdata->m_expression_len = len;
688 charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
689 m_pdata->m_expression = ps;
690 re_detail::copy(p1, p2, ps);
692 // fill in our other data...
693 // successful parsing implies a zero status:
694 m_pdata->m_status = 0;
695 // get the first state of the machine:
696 m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
697 // fixup pointers in the machine:
698 fixup_pointers(m_pdata->m_first_state);
701 m_pdata->m_has_recursions = true;
702 fixup_recursions(m_pdata->m_first_state);
703 if(this->m_pdata->m_status)
707 m_pdata->m_has_recursions = false;
708 // create nested startmaps:
709 create_startmaps(m_pdata->m_first_state);
710 // create main startmap:
711 std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
712 m_pdata->m_can_be_null = 0;
715 create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
716 // get the restart type:
717 m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
718 // optimise a leading repeat if there is one:
719 probe_leading_repeat(m_pdata->m_first_state);
722 template <class charT, class traits>
723 void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
729 case syntax_element_recurse:
730 m_has_recursions = true;
732 state->next.p = getaddress(state->next.i, state);
736 case syntax_element_rep:
737 case syntax_element_dot_rep:
738 case syntax_element_char_rep:
739 case syntax_element_short_set_rep:
740 case syntax_element_long_set_rep:
741 // set the state_id of this repeat:
742 static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
744 case syntax_element_alt:
745 std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
746 static_cast<re_alt*>(state)->can_be_null = 0;
748 case syntax_element_jump:
749 static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
750 // fall through again:
753 state->next.p = getaddress(state->next.i, state);
757 state = state->next.p;
761 template <class charT, class traits>
762 void basic_regex_creator<charT, traits>::fixup_recursions(re_syntax_base* state)
764 re_syntax_base* base = state;
769 case syntax_element_assert_backref:
771 // just check that the index is valid:
772 int idx = static_cast<const re_brace*>(state)->index;
778 idx = m_pdata->get_id(idx);
781 // check of sub-expression that doesn't exist:
782 if(0 == this->m_pdata->m_status) // update the error code if not already set
783 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
785 // clear the expression, we should be empty:
787 this->m_pdata->m_expression = 0;
788 this->m_pdata->m_expression_len = 0;
790 // and throw if required:
792 if(0 == (this->flags() & regex_constants::no_except))
794 std::string message = "Encountered a forward reference to a marked sub-expression that does not exist.";
795 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
803 case syntax_element_recurse:
806 re_syntax_base* p = base;
807 std::ptrdiff_t idx = static_cast<re_jump*>(state)->alt.i;
809 idx = m_pdata->get_id(idx);
812 if((p->type == syntax_element_startmark) && (static_cast<re_brace*>(p)->index == idx))
815 // We've found the target of the recursion, set the jump target:
817 static_cast<re_jump*>(state)->alt.p = p;
820 // Now scan the target for nested repeats:
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;
835 case syntax_element_endmark:
836 if(static_cast<const re_brace*>(p)->index == idx)
848 static_cast<re_recurse*>(state)->state_id = next_rep_id - 1;
857 // recursion to sub-expression that doesn't exist:
858 if(0 == this->m_pdata->m_status) // update the error code if not already set
859 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
861 // clear the expression, we should be empty:
863 this->m_pdata->m_expression = 0;
864 this->m_pdata->m_expression_len = 0;
866 // and throw if required:
868 if(0 == (this->flags() & regex_constants::no_except))
870 std::string message = "Encountered a forward reference to a recursive sub-expression that does not exist.";
871 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
879 state = state->next.p;
883 template <class charT, class traits>
884 void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
886 // non-recursive implementation:
887 // create the last map in the machine first, so that earlier maps
888 // can make use of the result...
890 // This was originally a recursive implementation, but that caused stack
891 // overflows with complex expressions on small stacks (think COM+).
893 // start by saving the case setting:
894 bool l_icase = m_icase;
895 std::vector<std::pair<bool, re_syntax_base*> > v;
901 case syntax_element_toggle_case:
902 // we need to track case changes here:
903 m_icase = static_cast<re_case*>(state)->icase;
904 state = state->next.p;
906 case syntax_element_alt:
907 case syntax_element_rep:
908 case syntax_element_dot_rep:
909 case syntax_element_char_rep:
910 case syntax_element_short_set_rep:
911 case syntax_element_long_set_rep:
912 // just push the state onto our stack for now:
913 v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
914 state = state->next.p;
916 case syntax_element_backstep:
917 // we need to calculate how big the backstep is:
918 static_cast<re_brace*>(state)->index
919 = this->calculate_backstep(state->next.p);
920 if(static_cast<re_brace*>(state)->index < 0)
923 if(0 == this->m_pdata->m_status) // update the error code if not already set
924 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
926 // clear the expression, we should be empty:
928 this->m_pdata->m_expression = 0;
929 this->m_pdata->m_expression_len = 0;
931 // and throw if required:
933 if(0 == (this->flags() & regex_constants::no_except))
935 std::string message = "Invalid lookbehind assertion encountered in the regular expression.";
936 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
942 state = state->next.p;
945 // now work through our list, building all the maps as we go:
948 const std::pair<bool, re_syntax_base*>& p = v.back();
955 create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
957 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);
958 // adjust the type of the state to allow for faster matching:
959 state->type = this->get_repeat_type(state);
961 // restore case sensitivity:
965 template <class charT, class traits>
966 int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
968 typedef typename traits::char_class_type mask_type;
974 case syntax_element_startmark:
975 if((static_cast<re_brace*>(state)->index == -1)
976 || (static_cast<re_brace*>(state)->index == -2))
978 state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
981 else if(static_cast<re_brace*>(state)->index == -3)
983 state = state->next.p->next.p;
987 case syntax_element_endmark:
988 if((static_cast<re_brace*>(state)->index == -1)
989 || (static_cast<re_brace*>(state)->index == -2))
992 case syntax_element_literal:
993 result += static_cast<re_literal*>(state)->length;
995 case syntax_element_wild:
996 case syntax_element_set:
999 case syntax_element_dot_rep:
1000 case syntax_element_char_rep:
1001 case syntax_element_short_set_rep:
1002 case syntax_element_backref:
1003 case syntax_element_rep:
1004 case syntax_element_combining:
1005 case syntax_element_long_set_rep:
1006 case syntax_element_backstep:
1008 re_repeat* rep = static_cast<re_repeat *>(state);
1009 // adjust the type of the state to allow for faster matching:
1010 state->type = this->get_repeat_type(state);
1011 if((state->type == syntax_element_dot_rep)
1012 || (state->type == syntax_element_char_rep)
1013 || (state->type == syntax_element_short_set_rep))
1015 if(rep->max != rep->min)
1017 result += static_cast<int>(rep->min);
1021 else if((state->type == syntax_element_long_set_rep))
1023 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
1024 if(static_cast<re_set_long<mask_type>*>(rep->next.p)->singleton == 0)
1026 if(rep->max != rep->min)
1028 result += static_cast<int>(rep->min);
1034 case syntax_element_long_set:
1035 if(static_cast<re_set_long<mask_type>*>(state)->singleton == 0)
1039 case syntax_element_jump:
1040 state = static_cast<re_jump*>(state)->alt.p;
1042 case syntax_element_alt:
1044 int r1 = calculate_backstep(state->next.p);
1045 int r2 = calculate_backstep(static_cast<re_alt*>(state)->alt.p);
1046 if((r1 < 0) || (r1 != r2))
1053 state = state->next.p;
1058 template <class charT, class traits>
1059 void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
1061 int not_last_jump = 1;
1062 re_syntax_base* recursion_start = 0;
1063 int recursion_sub = 0;
1064 re_syntax_base* recursion_restart = 0;
1066 // track case sensitivity:
1067 bool l_icase = m_icase;
1073 case syntax_element_toggle_case:
1074 l_icase = static_cast<re_case*>(state)->icase;
1075 state = state->next.p;
1077 case syntax_element_literal:
1079 // don't set anything in *pnull, set each element in l_map
1080 // that could match the first character in the literal:
1083 l_map[0] |= mask_init;
1084 charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
1085 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1087 if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
1093 case syntax_element_end_line:
1095 // next character must be a line separator (if there is one):
1098 l_map[0] |= mask_init;
1099 l_map['\n'] |= mask;
1100 l_map['\r'] |= mask;
1101 l_map['\f'] |= mask;
1102 l_map[0x85] |= mask;
1104 // now figure out if we can match a NULL string at this point:
1106 create_startmap(state->next.p, 0, pnull, mask);
1109 case syntax_element_recurse:
1111 if(recursion_start == state)
1113 // Infinite recursion!!
1114 if(0 == this->m_pdata->m_status) // update the error code if not already set
1115 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
1117 // clear the expression, we should be empty:
1119 this->m_pdata->m_expression = 0;
1120 this->m_pdata->m_expression_len = 0;
1122 // and throw if required:
1124 if(0 == (this->flags() & regex_constants::no_except))
1126 std::string message = "Encountered an infinite recursion.";
1127 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
1131 else if(recursion_start == 0)
1133 recursion_start = state;
1134 recursion_restart = state->next.p;
1135 state = static_cast<re_jump*>(state)->alt.p;
1136 if(state->type == syntax_element_startmark)
1137 recursion_sub = static_cast<re_brace*>(state)->index;
1142 // fall through, can't handle nested recursion here...
1144 case syntax_element_backref:
1145 // can be null, and any character can match:
1149 case syntax_element_wild:
1151 // can't be null, any character can match:
1152 set_all_masks(l_map, mask);
1155 case syntax_element_match:
1157 // must be null, any character can match:
1158 set_all_masks(l_map, mask);
1163 case syntax_element_word_start:
1165 // recurse, then AND with all the word characters:
1166 create_startmap(state->next.p, l_map, pnull, mask);
1169 l_map[0] |= mask_init;
1170 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1172 if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
1173 l_map[i] &= static_cast<unsigned char>(~mask);
1178 case syntax_element_word_end:
1180 // recurse, then AND with all the word characters:
1181 create_startmap(state->next.p, l_map, pnull, mask);
1184 l_map[0] |= mask_init;
1185 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1187 if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
1188 l_map[i] &= static_cast<unsigned char>(~mask);
1193 case syntax_element_buffer_end:
1195 // we *must be null* :
1200 case syntax_element_long_set:
1203 typedef typename traits::char_class_type mask_type;
1204 if(static_cast<re_set_long<mask_type>*>(state)->singleton)
1206 l_map[0] |= mask_init;
1207 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1209 charT c = static_cast<charT>(i);
1210 if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<mask_type>*>(state), *m_pdata, m_icase))
1215 set_all_masks(l_map, mask);
1218 case syntax_element_set:
1221 l_map[0] |= mask_init;
1222 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1224 if(static_cast<re_set*>(state)->_map[
1225 static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1230 case syntax_element_jump:
1232 state = static_cast<re_alt*>(state)->alt.p;
1235 case syntax_element_alt:
1236 case syntax_element_rep:
1237 case syntax_element_dot_rep:
1238 case syntax_element_char_rep:
1239 case syntax_element_short_set_rep:
1240 case syntax_element_long_set_rep:
1242 re_alt* rep = static_cast<re_alt*>(state);
1243 if(rep->_map[0] & mask_init)
1247 // copy previous results:
1248 l_map[0] |= mask_init;
1249 for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1251 if(rep->_map[i] & mask_any)
1257 if(rep->can_be_null & mask_any)
1263 // we haven't created a startmap for this alternative yet
1264 // so take the union of the two options:
1265 if(is_bad_repeat(state))
1267 set_all_masks(l_map, mask);
1272 set_bad_repeat(state);
1273 create_startmap(state->next.p, l_map, pnull, mask);
1274 if((state->type == syntax_element_alt)
1275 || (static_cast<re_repeat*>(state)->min == 0)
1276 || (not_last_jump == 0))
1277 create_startmap(rep->alt.p, l_map, pnull, mask);
1281 case syntax_element_soft_buffer_end:
1282 // match newline or null:
1285 l_map[0] |= mask_init;
1286 l_map['\n'] |= mask;
1287 l_map['\r'] |= mask;
1292 case syntax_element_endmark:
1293 // need to handle independent subs as a special case:
1294 if(static_cast<re_brace*>(state)->index < 0)
1296 // can be null, any character can match:
1297 set_all_masks(l_map, mask);
1302 else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast<re_brace*>(state)->index))
1304 // recursion termination:
1305 recursion_start = 0;
1306 state = recursion_restart;
1311 // Normally we just go to the next state... but if this sub-expression is
1312 // the target of a recursion, then we might be ending a recursion, in which
1313 // case we should check whatever follows that recursion, as well as whatever
1314 // follows this state:
1316 if(m_pdata->m_has_recursions && static_cast<re_brace*>(state)->index)
1319 re_syntax_base* p = m_pdata->m_first_state;
1322 if((p->type == syntax_element_recurse))
1324 re_brace* p2 = static_cast<re_brace*>(static_cast<re_jump*>(p)->alt.p);
1325 if((p2->type == syntax_element_startmark) && (p2->index == static_cast<re_brace*>(state)->index))
1335 create_startmap(p->next.p, l_map, pnull, mask);
1338 state = state->next.p;
1341 case syntax_element_startmark:
1342 // need to handle independent subs as a special case:
1343 if(static_cast<re_brace*>(state)->index == -3)
1345 state = state->next.p->next.p;
1348 // otherwise fall through:
1350 state = state->next.p;
1356 template <class charT, class traits>
1357 unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1360 // find out how the machine starts, so we can optimise the search:
1366 case syntax_element_startmark:
1367 case syntax_element_endmark:
1368 state = state->next.p;
1370 case syntax_element_start_line:
1371 return regbase::restart_line;
1372 case syntax_element_word_start:
1373 return regbase::restart_word;
1374 case syntax_element_buffer_start:
1375 return regbase::restart_buf;
1376 case syntax_element_restart_continue:
1377 return regbase::restart_continue;
1383 return regbase::restart_any;
1386 template <class charT, class traits>
1387 void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1390 // set mask in all of bits elements,
1391 // if bits[0] has mask_init not set then we can
1392 // optimise this to a call to memset:
1397 (std::memset)(bits, mask, 1u << CHAR_BIT);
1400 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1403 bits[0] |= mask_init;
1407 template <class charT, class traits>
1408 bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1412 case syntax_element_rep:
1413 case syntax_element_dot_rep:
1414 case syntax_element_char_rep:
1415 case syntax_element_short_set_rep:
1416 case syntax_element_long_set_rep:
1418 unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1419 if(state_id > sizeof(m_bad_repeats) * CHAR_BIT)
1420 return true; // run out of bits, assume we can't traverse this one.
1421 static const boost::uintmax_t one = 1uL;
1422 return m_bad_repeats & (one << state_id);
1429 template <class charT, class traits>
1430 void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1434 case syntax_element_rep:
1435 case syntax_element_dot_rep:
1436 case syntax_element_char_rep:
1437 case syntax_element_short_set_rep:
1438 case syntax_element_long_set_rep:
1440 unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
1441 static const boost::uintmax_t one = 1uL;
1442 if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
1443 m_bad_repeats |= (one << state_id);
1450 template <class charT, class traits>
1451 syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1453 typedef typename traits::char_class_type mask_type;
1454 if(state->type == syntax_element_rep)
1456 // check to see if we are repeating a single state:
1457 if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1459 switch(state->next.p->type)
1461 case re_detail::syntax_element_wild:
1462 return re_detail::syntax_element_dot_rep;
1463 case re_detail::syntax_element_literal:
1464 return re_detail::syntax_element_char_rep;
1465 case re_detail::syntax_element_set:
1466 return re_detail::syntax_element_short_set_rep;
1467 case re_detail::syntax_element_long_set:
1468 if(static_cast<re_detail::re_set_long<mask_type>*>(state->next.p)->singleton)
1469 return re_detail::syntax_element_long_set_rep;
1479 template <class charT, class traits>
1480 void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1482 // enumerate our states, and see if we have a leading repeat
1483 // for which failed search restarts can be optimised;
1488 case syntax_element_startmark:
1489 if(static_cast<re_brace*>(state)->index >= 0)
1491 state = state->next.p;
1494 if((static_cast<re_brace*>(state)->index == -1)
1495 || (static_cast<re_brace*>(state)->index == -2))
1497 // skip past the zero width assertion:
1498 state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
1501 if(static_cast<re_brace*>(state)->index == -3)
1503 // Have to skip the leading jump state:
1504 state = state->next.p->next.p;
1508 case syntax_element_endmark:
1509 case syntax_element_start_line:
1510 case syntax_element_end_line:
1511 case syntax_element_word_boundary:
1512 case syntax_element_within_word:
1513 case syntax_element_word_start:
1514 case syntax_element_word_end:
1515 case syntax_element_buffer_start:
1516 case syntax_element_buffer_end:
1517 case syntax_element_restart_continue:
1518 state = state->next.p;
1520 case syntax_element_dot_rep:
1521 case syntax_element_char_rep:
1522 case syntax_element_short_set_rep:
1523 case syntax_element_long_set_rep:
1524 if(this->m_has_backrefs == 0)
1525 static_cast<re_repeat*>(state)->leading = true;
1534 } // namespace re_detail
1536 } // namespace boost
1539 # pragma warning(pop)
1543 #pragma warning(push)
1544 #pragma warning(disable: 4103)
1546 #ifdef BOOST_HAS_ABI_HEADERS
1547 # include BOOST_ABI_SUFFIX
1550 #pragma warning(pop)