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 #ifdef BOOST_HAS_ABI_HEADERS
24 # include BOOST_ABI_PREFIX
31 template <class charT>
32 struct digraph : public std::pair<charT, charT>
34 digraph() : std::pair<charT, charT>(0, 0){}
35 digraph(charT c1) : std::pair<charT, charT>(c1, 0){}
36 digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
38 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
39 digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
42 digraph(const Seq& s) : std::pair<charT, charT>()
44 BOOST_ASSERT(s.size() <= 2);
45 BOOST_ASSERT(s.size());
47 this->second = (s.size() > 1) ? s[1] : 0;
51 template <class charT, class traits>
55 typedef digraph<charT> digraph_type;
56 typedef typename traits::string_type string_type;
57 typedef typename traits::char_class_type mask_type;
62 m_has_digraphs = false;
64 m_negated_classes = 0;
68 void add_single(const digraph_type& s)
70 m_singles.insert(m_singles.end(), s);
72 m_has_digraphs = true;
75 void add_range(const digraph_type& first, const digraph_type& end)
77 m_ranges.insert(m_ranges.end(), first);
78 m_ranges.insert(m_ranges.end(), end);
81 m_has_digraphs = true;
86 m_has_digraphs = true;
91 void add_class(mask_type m)
96 void add_negated_class(mask_type m)
98 m_negated_classes |= m;
101 void add_equivalent(const digraph_type& s)
103 m_equivalents.insert(m_equivalents.end(), s);
106 m_has_digraphs = true;
118 // accessor functions:
120 bool has_digraphs()const
122 return m_has_digraphs;
124 bool is_negated()const
128 typedef typename std::vector<digraph_type>::const_iterator list_iterator;
129 list_iterator singles_begin()const
131 return m_singles.begin();
133 list_iterator singles_end()const
135 return m_singles.end();
137 list_iterator ranges_begin()const
139 return m_ranges.begin();
141 list_iterator ranges_end()const
143 return m_ranges.end();
145 list_iterator equivalents_begin()const
147 return m_equivalents.begin();
149 list_iterator equivalents_end()const
151 return m_equivalents.end();
153 mask_type classes()const
157 mask_type negated_classes()const
159 return m_negated_classes;
166 std::vector<digraph_type> m_singles; // a list of single characters to match
167 std::vector<digraph_type> m_ranges; // a list of end points of our ranges
168 bool m_negate; // true if the set is to be negated
169 bool m_has_digraphs; // true if we have digraphs present
170 mask_type m_classes; // character classes to match
171 mask_type m_negated_classes; // negated character classes to match
172 bool m_empty; // whether we've added anything yet
173 std::vector<digraph_type> m_equivalents; // a list of equivalence classes
176 template <class charT, class traits>
177 class basic_regex_creator
180 basic_regex_creator(regex_data<charT, traits>* data);
181 std::ptrdiff_t getoffset(void* addr)
183 return getoffset(addr, m_pdata->m_data.data());
185 std::ptrdiff_t getoffset(const void* addr, const void* base)
187 return static_cast<const char*>(addr) - static_cast<const char*>(base);
189 re_syntax_base* getaddress(std::ptrdiff_t off)
191 return getaddress(off, m_pdata->m_data.data());
193 re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
195 return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
197 void init(unsigned l_flags)
199 m_pdata->m_flags = l_flags;
200 m_icase = l_flags & regex_constants::icase;
202 regbase::flag_type flags()
204 return m_pdata->m_flags;
206 void flags(regbase::flag_type f)
208 m_pdata->m_flags = f;
209 if(m_icase != static_cast<bool>(f & regbase::icase))
211 m_icase = static_cast<bool>(f & regbase::icase);
214 re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
215 re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
216 re_literal* append_literal(charT c);
217 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
218 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
219 re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
220 void finalize(const charT* p1, const charT* p2);
222 regex_data<charT, traits>* m_pdata; // pointer to the basic_regex_data struct we are filling in
223 const ::boost::regex_traits_wrapper<traits>&
224 m_traits; // convenience reference to traits class
225 re_syntax_base* m_last_state; // the last state we added
226 bool m_icase; // true for case insensitive matches
227 unsigned m_repeater_id; // the id of the next repeater
228 bool m_has_backrefs; // true if there are actually any backrefs
229 unsigned m_backrefs; // bitmask of permitted backrefs
230 boost::uintmax_t m_bad_repeats; // bitmask of repeats we can't deduce a startmap for;
231 typename traits::char_class_type m_word_mask; // mask used to determine if a character is a word character
232 typename traits::char_class_type m_mask_space; // mask used to determine if a character is a word character
233 typename traits::char_class_type m_lower_mask; // mask used to determine if a character is a lowercase character
234 typename traits::char_class_type m_upper_mask; // mask used to determine if a character is an uppercase character
235 typename traits::char_class_type m_alpha_mask; // mask used to determine if a character is an alphabetic character
237 basic_regex_creator& operator=(const basic_regex_creator&);
238 basic_regex_creator(const basic_regex_creator&);
240 void fixup_pointers(re_syntax_base* state);
241 void create_startmaps(re_syntax_base* state);
242 int calculate_backstep(re_syntax_base* state);
243 void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
244 unsigned get_restart_type(re_syntax_base* state);
245 void set_all_masks(unsigned char* bits, unsigned char);
246 bool is_bad_repeat(re_syntax_base* pt);
247 void set_bad_repeat(re_syntax_base* pt);
248 syntax_element_type get_repeat_type(re_syntax_base* state);
249 void probe_leading_repeat(re_syntax_base* state);
252 template <class charT, class traits>
253 basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
254 : m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_repeater_id(0), m_has_backrefs(false), m_backrefs(0)
256 m_pdata->m_data.clear();
257 m_pdata->m_status = ::boost::regex_constants::error_ok;
258 static const charT w = 'w';
259 static const charT s = 's';
260 static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
261 static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
262 static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
263 m_word_mask = m_traits.lookup_classname(&w, &w +1);
264 m_mask_space = m_traits.lookup_classname(&s, &s +1);
265 m_lower_mask = m_traits.lookup_classname(l, l + 5);
266 m_upper_mask = m_traits.lookup_classname(u, u + 5);
267 m_alpha_mask = m_traits.lookup_classname(a, a + 5);
268 m_pdata->m_word_mask = m_word_mask;
269 BOOST_ASSERT(m_word_mask != 0);
270 BOOST_ASSERT(m_mask_space != 0);
271 BOOST_ASSERT(m_lower_mask != 0);
272 BOOST_ASSERT(m_upper_mask != 0);
273 BOOST_ASSERT(m_alpha_mask != 0);
276 template <class charT, class traits>
277 re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
279 // if the state is a backref then make a note of it:
280 if(t == syntax_element_backref)
281 this->m_has_backrefs = true;
282 // append a new state, start by aligning our last one:
283 m_pdata->m_data.align();
284 // set the offset to the next state in our last one:
286 m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
287 // now actually extent our data:
288 m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
289 // fill in boilerplate options in the new state:
290 m_last_state->next.i = 0;
291 m_last_state->type = t;
295 template <class charT, class traits>
296 re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
298 // append a new state, start by aligning our last one:
299 m_pdata->m_data.align();
300 // set the offset to the next state in our last one:
302 m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
303 // remember the last state position:
304 std::ptrdiff_t off = getoffset(m_last_state) + s;
305 // now actually insert our data:
306 re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
307 // fill in boilerplate options in the new state:
308 new_state->next.i = s;
310 m_last_state = getaddress(off);
314 template <class charT, class traits>
315 re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
318 // start by seeing if we have an existing re_literal we can extend:
319 if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
321 // no existing re_literal, create a new one:
322 result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
324 *static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
328 // we have an existing re_literal, extend it:
329 std::ptrdiff_t off = getoffset(m_last_state);
330 m_pdata->m_data.extend(sizeof(charT));
331 m_last_state = result = static_cast<re_literal*>(getaddress(off));
332 charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
333 characters[result->length] = m_traits.translate(c, m_icase);
339 template <class charT, class traits>
340 inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
341 const basic_char_set<charT, traits>& char_set)
343 typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
344 return char_set.has_digraphs()
345 ? append_set(char_set, static_cast<mpl::false_*>(0))
346 : append_set(char_set, static_cast<truth_type*>(0));
349 template <class charT, class traits>
350 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
351 const basic_char_set<charT, traits>& char_set, mpl::false_*)
353 typedef typename traits::string_type string_type;
354 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
355 typedef typename traits::char_class_type mask_type;
357 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>)));
359 // fill in the basics:
361 result->csingles = static_cast<unsigned int>(::boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end()));
362 result->cranges = static_cast<unsigned int>(::boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
363 result->cequivalents = static_cast<unsigned int>(::boost::re_detail::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
364 result->cclasses = char_set.classes();
365 result->cnclasses = char_set.negated_classes();
366 if(flags() & regbase::icase)
368 // adjust classes as needed:
369 if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
370 result->cclasses |= m_alpha_mask;
371 if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
372 result->cnclasses |= m_alpha_mask;
375 result->isnot = char_set.is_negated();
376 result->singleton = !char_set.has_digraphs();
378 // remember where the state is for later:
380 std::ptrdiff_t offset = getoffset(result);
382 // now extend with all the singles:
384 item_iterator first, last;
385 first = char_set.singles_begin();
386 last = char_set.singles_end();
389 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (first->second ? 3 : 2)));
390 p[0] = m_traits.translate(first->first, m_icase);
393 p[1] = m_traits.translate(first->second, m_icase);
401 // now extend with all the ranges:
403 first = char_set.ranges_begin();
404 last = char_set.ranges_end();
407 // first grab the endpoints of the range:
408 digraph<charT> c1 = *first;
409 c1.first = this->m_traits.translate(c1.first, this->m_icase);
410 c1.second = this->m_traits.translate(c1.second, this->m_icase);
412 digraph<charT> c2 = *first;
413 c2.first = this->m_traits.translate(c2.first, this->m_icase);
414 c2.second = this->m_traits.translate(c2.second, this->m_icase);
417 // different actions now depending upon whether collation is turned on:
418 if(flags() & regex_constants::collate)
420 // we need to transform our range into sort keys:
421 #if BOOST_WORKAROUND(__GNUC__, < 3)
422 string_type in(3, charT(0));
425 s1 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
428 s2 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
430 charT a1[3] = { c1.first, c1.second, charT(0), };
431 charT a2[3] = { c2.first, c2.second, charT(0), };
432 s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
433 s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
436 s1 = string_type(1, charT(0));
438 s2 = string_type(1, charT(0));
444 s1.insert(s1.end(), c1.first);
445 s1.insert(s1.end(), c1.second);
448 s1 = string_type(1, c1.first);
451 s2.insert(s2.end(), c2.first);
452 s2.insert(s2.end(), c2.second);
455 s2.insert(s2.end(), c2.first);
462 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
463 re_detail::copy(s1.begin(), s1.end(), p);
464 p[s1.size()] = charT(0);
466 re_detail::copy(s2.begin(), s2.end(), p);
467 p[s2.size()] = charT(0);
470 // now process the equivalence classes:
472 first = char_set.equivalents_begin();
473 last = char_set.equivalents_end();
479 #if BOOST_WORKAROUND(__GNUC__, < 3)
480 string_type in(3, charT(0));
481 in[0] = first->first;
482 in[1] = first->second;
483 s = m_traits.transform_primary(in.c_str(), in.c_str()+2);
485 charT cs[3] = { first->first, first->second, charT(0), };
486 s = m_traits.transform_primary(cs, cs+2);
490 s = m_traits.transform_primary(&first->first, &first->first+1);
492 return 0; // invalid or unsupported equivalence class
493 charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
494 re_detail::copy(s.begin(), s.end(), p);
495 p[s.size()] = charT(0);
499 // finally reset the address of our last state:
501 m_last_state = result = static_cast<re_set_long<mask_type>*>(getaddress(offset));
508 inline bool char_less(T t1, T t2)
513 inline bool char_less<char>(char t1, char t2)
515 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
518 inline bool char_less<signed char>(signed char t1, signed char t2)
520 return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
524 template <class charT, class traits>
525 re_syntax_base* basic_regex_creator<charT, traits>::append_set(
526 const basic_char_set<charT, traits>& char_set, mpl::true_*)
528 typedef typename traits::string_type string_type;
529 typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
531 re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
532 bool negate = char_set.is_negated();
533 std::memset(result->_map, 0, sizeof(result->_map));
535 // handle singles first:
537 item_iterator first, last;
538 first = char_set.singles_begin();
539 last = char_set.singles_end();
542 for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
544 if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
545 == this->m_traits.translate(first->first, this->m_icase))
546 result->_map[i] = true;
551 // OK now handle ranges:
553 first = char_set.ranges_begin();
554 last = char_set.ranges_end();
557 // first grab the endpoints of the range:
558 charT c1 = this->m_traits.translate(first->first, this->m_icase);
560 charT c2 = this->m_traits.translate(first->first, this->m_icase);
562 // different actions now depending upon whether collation is turned on:
563 if(flags() & regex_constants::collate)
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);
569 string_type s2 = this->m_traits.transform(c3, c3+1);
575 BOOST_ASSERT(c3[1] == charT(0));
576 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
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;
586 if(char_less<charT>(c2, c1))
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));
596 // and now the classes:
598 typedef typename traits::char_class_type mask_type;
599 mask_type m = char_set.classes();
600 if(flags() & regbase::icase)
602 // adjust m as needed:
603 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
608 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
610 if(this->m_traits.isctype(static_cast<charT>(i), m))
611 result->_map[i] = true;
615 // and now the negated classes:
617 m = char_set.negated_classes();
618 if(flags() & regbase::icase)
620 // adjust m as needed:
621 if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
626 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
628 if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
629 result->_map[i] = true;
633 // now process the equivalence classes:
635 first = char_set.equivalents_begin();
636 last = char_set.equivalents_end();
640 BOOST_ASSERT(static_cast<charT>(0) == first->second);
641 s = m_traits.transform_primary(&first->first, &first->first+1);
643 return 0; // invalid or unsupported equivalence class
644 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
646 charT c[2] = { (static_cast<charT>(i)), charT(0), };
647 string_type s2 = this->m_traits.transform_primary(c, c+1);
649 result->_map[i] = true;
655 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
657 result->_map[i] = !(result->_map[i]);
663 template <class charT, class traits>
664 void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
666 // we've added all the states we need, now finish things off.
667 // start by adding a terminating state:
668 append_state(syntax_element_match);
669 // extend storage to store original expression:
670 std::ptrdiff_t len = p2 - p1;
671 m_pdata->m_expression_len = len;
672 charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
673 m_pdata->m_expression = ps;
674 re_detail::copy(p1, p2, ps);
676 // fill in our other data...
677 // successful parsing implies a zero status:
678 m_pdata->m_status = 0;
679 // get the first state of the machine:
680 m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
681 // fixup pointers in the machine:
682 fixup_pointers(m_pdata->m_first_state);
683 // create nested startmaps:
684 create_startmaps(m_pdata->m_first_state);
685 // create main startmap:
686 std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
687 m_pdata->m_can_be_null = 0;
690 create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
691 // get the restart type:
692 m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
693 // optimise a leading repeat if there is one:
694 probe_leading_repeat(m_pdata->m_first_state);
697 template <class charT, class traits>
698 void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
704 case syntax_element_rep:
705 case syntax_element_dot_rep:
706 case syntax_element_char_rep:
707 case syntax_element_short_set_rep:
708 case syntax_element_long_set_rep:
709 // set the id of this repeat:
710 static_cast<re_repeat*>(state)->id = m_repeater_id++;
712 case syntax_element_alt:
713 std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
714 static_cast<re_alt*>(state)->can_be_null = 0;
716 case syntax_element_jump:
717 static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
718 // fall through again:
721 state->next.p = getaddress(state->next.i, state);
725 state = state->next.p;
729 template <class charT, class traits>
730 void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
732 // non-recursive implementation:
733 // create the last map in the machine first, so that earlier maps
734 // can make use of the result...
736 // This was originally a recursive implementation, but that caused stack
737 // overflows with complex expressions on small stacks (think COM+).
739 // start by saving the case setting:
740 bool l_icase = m_icase;
741 std::vector<std::pair<bool, re_syntax_base*> > v;
747 case syntax_element_toggle_case:
748 // we need to track case changes here:
749 m_icase = static_cast<re_case*>(state)->icase;
750 state = state->next.p;
752 case syntax_element_alt:
753 case syntax_element_rep:
754 case syntax_element_dot_rep:
755 case syntax_element_char_rep:
756 case syntax_element_short_set_rep:
757 case syntax_element_long_set_rep:
758 // just push the state onto our stack for now:
759 v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
760 state = state->next.p;
762 case syntax_element_backstep:
763 // we need to calculate how big the backstep is:
764 static_cast<re_brace*>(state)->index
765 = this->calculate_backstep(state->next.p);
766 if(static_cast<re_brace*>(state)->index < 0)
769 if(0 == this->m_pdata->m_status) // update the error code if not already set
770 this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
772 // clear the expression, we should be empty:
774 this->m_pdata->m_expression = 0;
775 this->m_pdata->m_expression_len = 0;
777 // and throw if required:
779 if(0 == (this->flags() & regex_constants::no_except))
781 std::string message = this->m_pdata->m_ptraits->error_string(boost::regex_constants::error_bad_pattern);
782 boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
788 state = state->next.p;
791 // now work through our list, building all the maps as we go:
794 const std::pair<bool, re_syntax_base*>& p = v.back();
801 create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
803 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);
804 // adjust the type of the state to allow for faster matching:
805 state->type = this->get_repeat_type(state);
807 // restore case sensitivity:
811 template <class charT, class traits>
812 int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
814 typedef typename traits::char_class_type mask_type;
820 case syntax_element_startmark:
821 if((static_cast<re_brace*>(state)->index == -1)
822 || (static_cast<re_brace*>(state)->index == -2))
824 state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
827 else if(static_cast<re_brace*>(state)->index == -3)
829 state = state->next.p->next.p;
833 case syntax_element_endmark:
834 if((static_cast<re_brace*>(state)->index == -1)
835 || (static_cast<re_brace*>(state)->index == -2))
838 case syntax_element_literal:
839 result += static_cast<re_literal*>(state)->length;
841 case syntax_element_wild:
842 case syntax_element_set:
845 case syntax_element_dot_rep:
846 case syntax_element_char_rep:
847 case syntax_element_short_set_rep:
848 case syntax_element_backref:
849 case syntax_element_rep:
850 case syntax_element_combining:
851 case syntax_element_long_set_rep:
852 case syntax_element_backstep:
854 re_repeat* rep = static_cast<re_repeat *>(state);
855 // adjust the type of the state to allow for faster matching:
856 state->type = this->get_repeat_type(state);
857 if((state->type == syntax_element_dot_rep)
858 || (state->type == syntax_element_char_rep)
859 || (state->type == syntax_element_short_set_rep))
861 if(rep->max != rep->min)
863 result += static_cast<int>(rep->min);
867 else if((state->type == syntax_element_long_set_rep))
869 BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
870 if(static_cast<re_set_long<mask_type>*>(rep->next.p)->singleton == 0)
872 if(rep->max != rep->min)
874 result += static_cast<int>(rep->min);
880 case syntax_element_long_set:
881 if(static_cast<re_set_long<mask_type>*>(state)->singleton == 0)
885 case syntax_element_jump:
886 state = static_cast<re_jump*>(state)->alt.p;
891 state = state->next.p;
896 template <class charT, class traits>
897 void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
899 int not_last_jump = 1;
901 // track case sensitivity:
902 bool l_icase = m_icase;
908 case syntax_element_toggle_case:
909 l_icase = static_cast<re_case*>(state)->icase;
910 state = state->next.p;
912 case syntax_element_literal:
914 // don't set anything in *pnull, set each element in l_map
915 // that could match the first character in the literal:
918 l_map[0] |= mask_init;
919 charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
920 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
922 if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
928 case syntax_element_end_line:
930 // next character must be a line separator (if there is one):
933 l_map[0] |= mask_init;
939 // now figure out if we can match a NULL string at this point:
941 create_startmap(state->next.p, 0, pnull, mask);
944 case syntax_element_backref:
945 // can be null, and any character can match:
949 case syntax_element_wild:
951 // can't be null, any character can match:
952 set_all_masks(l_map, mask);
955 case syntax_element_match:
957 // must be null, any character can match:
958 set_all_masks(l_map, mask);
963 case syntax_element_word_start:
965 // recurse, then AND with all the word characters:
966 create_startmap(state->next.p, l_map, pnull, mask);
969 l_map[0] |= mask_init;
970 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
972 if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
973 l_map[i] &= static_cast<unsigned char>(~mask);
978 case syntax_element_word_end:
980 // recurse, then AND with all the word characters:
981 create_startmap(state->next.p, l_map, pnull, mask);
984 l_map[0] |= mask_init;
985 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
987 if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
988 l_map[i] &= static_cast<unsigned char>(~mask);
993 case syntax_element_buffer_end:
995 // we *must be null* :
1000 case syntax_element_long_set:
1003 typedef typename traits::char_class_type mask_type;
1004 if(static_cast<re_set_long<mask_type>*>(state)->singleton)
1006 l_map[0] |= mask_init;
1007 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1009 charT c = static_cast<charT>(i);
1010 if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<mask_type>*>(state), *m_pdata, m_icase))
1015 set_all_masks(l_map, mask);
1018 case syntax_element_set:
1021 l_map[0] |= mask_init;
1022 for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
1024 if(static_cast<re_set*>(state)->_map[
1025 static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
1030 case syntax_element_jump:
1032 state = static_cast<re_alt*>(state)->alt.p;
1035 case syntax_element_alt:
1036 case syntax_element_rep:
1037 case syntax_element_dot_rep:
1038 case syntax_element_char_rep:
1039 case syntax_element_short_set_rep:
1040 case syntax_element_long_set_rep:
1042 re_alt* rep = static_cast<re_alt*>(state);
1043 if(rep->_map[0] & mask_init)
1047 // copy previous results:
1048 l_map[0] |= mask_init;
1049 for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
1051 if(rep->_map[i] & mask_any)
1057 if(rep->can_be_null & mask_any)
1063 // we haven't created a startmap for this alternative yet
1064 // so take the union of the two options:
1065 if(is_bad_repeat(state))
1067 set_all_masks(l_map, mask);
1072 set_bad_repeat(state);
1073 create_startmap(state->next.p, l_map, pnull, mask);
1074 if((state->type == syntax_element_alt)
1075 || (static_cast<re_repeat*>(state)->min == 0)
1076 || (not_last_jump == 0))
1077 create_startmap(rep->alt.p, l_map, pnull, mask);
1081 case syntax_element_soft_buffer_end:
1082 // match newline or null:
1085 l_map[0] |= mask_init;
1086 l_map['\n'] |= mask;
1087 l_map['\r'] |= mask;
1092 case syntax_element_endmark:
1093 // need to handle independent subs as a special case:
1094 if(static_cast<re_brace*>(state)->index < 0)
1096 // can be null, any character can match:
1097 set_all_masks(l_map, mask);
1104 state = state->next.p;
1108 case syntax_element_startmark:
1109 // need to handle independent subs as a special case:
1110 if(static_cast<re_brace*>(state)->index == -3)
1112 state = state->next.p->next.p;
1115 // otherwise fall through:
1117 state = state->next.p;
1123 template <class charT, class traits>
1124 unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
1127 // find out how the machine starts, so we can optimise the search:
1133 case syntax_element_startmark:
1134 case syntax_element_endmark:
1135 state = state->next.p;
1137 case syntax_element_start_line:
1138 return regbase::restart_line;
1139 case syntax_element_word_start:
1140 return regbase::restart_word;
1141 case syntax_element_buffer_start:
1142 return regbase::restart_buf;
1143 case syntax_element_restart_continue:
1144 return regbase::restart_continue;
1150 return regbase::restart_any;
1153 template <class charT, class traits>
1154 void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
1157 // set mask in all of bits elements,
1158 // if bits[0] has mask_init not set then we can
1159 // optimise this to a call to memset:
1164 (std::memset)(bits, mask, 1u << CHAR_BIT);
1167 for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
1170 bits[0] |= mask_init;
1174 template <class charT, class traits>
1175 bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
1179 case syntax_element_rep:
1180 case syntax_element_dot_rep:
1181 case syntax_element_char_rep:
1182 case syntax_element_short_set_rep:
1183 case syntax_element_long_set_rep:
1185 unsigned id = static_cast<re_repeat*>(pt)->id;
1186 if(id > sizeof(m_bad_repeats) * CHAR_BIT)
1187 return true; // run out of bits, assume we can't traverse this one.
1188 static const boost::uintmax_t one = 1uL;
1189 return m_bad_repeats & (one << id);
1196 template <class charT, class traits>
1197 void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
1201 case syntax_element_rep:
1202 case syntax_element_dot_rep:
1203 case syntax_element_char_rep:
1204 case syntax_element_short_set_rep:
1205 case syntax_element_long_set_rep:
1207 unsigned id = static_cast<re_repeat*>(pt)->id;
1208 static const boost::uintmax_t one = 1uL;
1209 if(id <= sizeof(m_bad_repeats) * CHAR_BIT)
1210 m_bad_repeats |= (one << id);
1217 template <class charT, class traits>
1218 syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
1220 typedef typename traits::char_class_type mask_type;
1221 if(state->type == syntax_element_rep)
1223 // check to see if we are repeating a single state:
1224 if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
1226 switch(state->next.p->type)
1228 case re_detail::syntax_element_wild:
1229 return re_detail::syntax_element_dot_rep;
1230 case re_detail::syntax_element_literal:
1231 return re_detail::syntax_element_char_rep;
1232 case re_detail::syntax_element_set:
1233 return re_detail::syntax_element_short_set_rep;
1234 case re_detail::syntax_element_long_set:
1235 if(static_cast<re_detail::re_set_long<mask_type>*>(state->next.p)->singleton)
1236 return re_detail::syntax_element_long_set_rep;
1246 template <class charT, class traits>
1247 void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
1249 // enumerate our states, and see if we have a leading repeat
1250 // for which failed search restarts can be optimised;
1255 case syntax_element_startmark:
1256 if(static_cast<re_brace*>(state)->index >= 0)
1258 state = state->next.p;
1262 case syntax_element_endmark:
1263 case syntax_element_start_line:
1264 case syntax_element_end_line:
1265 case syntax_element_word_boundary:
1266 case syntax_element_within_word:
1267 case syntax_element_word_start:
1268 case syntax_element_word_end:
1269 case syntax_element_buffer_start:
1270 case syntax_element_buffer_end:
1271 case syntax_element_restart_continue:
1272 state = state->next.p;
1274 case syntax_element_dot_rep:
1275 case syntax_element_char_rep:
1276 case syntax_element_short_set_rep:
1277 case syntax_element_long_set_rep:
1278 if(this->m_has_backrefs == 0)
1279 static_cast<re_repeat*>(state)->leading = true;
1288 } // namespace re_detail
1290 } // namespace boost
1292 #ifdef BOOST_HAS_ABI_HEADERS
1293 # include BOOST_ABI_SUFFIX