FCL/sftools/dev/build: comparison imgtools/imglib/boostlibrary/boost/regex/v4/basic_regex

equal deleted inserted replaced

-:fa7a3cc6effd
+:6d08f4a05d93
+/*
+*
+* Copyright (c) 2004
+* John Maddock
+*
+* Use, modification and distribution are subject to the
+* Boost Software License, Version 1.0. (See accompanying file
+* LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+*
+*/
+/*
+*   LOCATION:    see http://www.boost.org for most recent version.
+*   FILE         basic_regex_creator.cpp
+*   VERSION      see <boost/version.hpp>
+*   DESCRIPTION: Declares template class basic_regex_creator which fills in
+*                the data members of a regex_data object.
+*/
+#ifndef BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
+#define BOOST_REGEX_V4_BASIC_REGEX_CREATOR_HPP
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable: 4103)
+#endif
+#ifdef BOOST_HAS_ABI_HEADERS
+#  include BOOST_ABI_PREFIX
+#endif
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+#ifdef BOOST_MSVC
+#  pragma warning(push)
+#  pragma warning(disable: 4800)
+#endif
+namespace boost{
+namespace re_detail{
+template <class charT>
+struct digraph : public std::pair<charT, charT>
+{
+digraph() : std::pair<charT, charT>(0, 0){}
+digraph(charT c1) : std::pair<charT, charT>(c1, 0){}
+digraph(charT c1, charT c2) : std::pair<charT, charT>(c1, c2)
+{}
+#if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
+digraph(const digraph<charT>& d) : std::pair<charT, charT>(d.first, d.second){}
+#endif
+template <class Seq>
+digraph(const Seq& s) : std::pair<charT, charT>()
+{
+BOOST_ASSERT(s.size() <= 2);
+BOOST_ASSERT(s.size());
+this->first = s[0];
+this->second = (s.size() > 1) ? s[1] : 0;
+}
+};
+template <class charT, class traits>
+class basic_char_set
+{
+public:
+typedef digraph<charT>                   digraph_type;
+typedef typename traits::string_type     string_type;
+typedef typename traits::char_class_type mask_type;
+basic_char_set()
+{
+m_negate = false;
+m_has_digraphs = false;
+m_classes = 0;
+m_negated_classes = 0;
+m_empty = true;
+}
+void add_single(const digraph_type& s)
+{
+m_singles.insert(m_singles.end(), s);
+if(s.second)
+m_has_digraphs = true;
+m_empty = false;
+}
+void add_range(const digraph_type& first, const digraph_type& end)
+{
+m_ranges.insert(m_ranges.end(), first);
+m_ranges.insert(m_ranges.end(), end);
+if(first.second)
+{
+m_has_digraphs = true;
+add_single(first);
+}
+if(end.second)
+{
+m_has_digraphs = true;
+add_single(end);
+}
+m_empty = false;
+}
+void add_class(mask_type m)
+{
+m_classes |= m;
+m_empty = false;
+}
+void add_negated_class(mask_type m)
+{
+m_negated_classes |= m;
+m_empty = false;
+}
+void add_equivalent(const digraph_type& s)
+{
+m_equivalents.insert(m_equivalents.end(), s);
+if(s.second)
+{
+m_has_digraphs = true;
+add_single(s);
+}
+m_empty = false;
+}
+void negate()
+{
+m_negate = true;
+//m_empty = false;
+}
+//
+// accessor functions:
+//
+bool has_digraphs()const
+{
+return m_has_digraphs;
+}
+bool is_negated()const
+{
+return m_negate;
+}
+typedef typename std::vector<digraph_type>::const_iterator  list_iterator;
+list_iterator singles_begin()const
+{
+return m_singles.begin();
+}
+list_iterator singles_end()const
+{
+return m_singles.end();
+}
+list_iterator ranges_begin()const
+{
+return m_ranges.begin();
+}
+list_iterator ranges_end()const
+{
+return m_ranges.end();
+}
+list_iterator equivalents_begin()const
+{
+return m_equivalents.begin();
+}
+list_iterator equivalents_end()const
+{
+return m_equivalents.end();
+}
+mask_type classes()const
+{
+return m_classes;
+}
+mask_type negated_classes()const
+{
+return m_negated_classes;
+}
+bool empty()const
+{
+return m_empty;
+}
+private:
+std::vector<digraph_type> m_singles;         // a list of single characters to match
+std::vector<digraph_type> m_ranges;          // a list of end points of our ranges
+bool                      m_negate;          // true if the set is to be negated
+bool                      m_has_digraphs;    // true if we have digraphs present
+mask_type                 m_classes;         // character classes to match
+mask_type                 m_negated_classes; // negated character classes to match
+bool                      m_empty;           // whether we've added anything yet
+std::vector<digraph_type> m_equivalents;     // a list of equivalence classes
+};
+template <class charT, class traits>
+class basic_regex_creator
+{
+public:
+basic_regex_creator(regex_data<charT, traits>* data);
+std::ptrdiff_t getoffset(void* addr)
+{
+return getoffset(addr, m_pdata->m_data.data());
+}
+std::ptrdiff_t getoffset(const void* addr, const void* base)
+{
+return static_cast<const char*>(addr) - static_cast<const char*>(base);
+}
+re_syntax_base* getaddress(std::ptrdiff_t off)
+{
+return getaddress(off, m_pdata->m_data.data());
+}
+re_syntax_base* getaddress(std::ptrdiff_t off, void* base)
+{
+return static_cast<re_syntax_base*>(static_cast<void*>(static_cast<char*>(base) + off));
+}
+void init(unsigned l_flags)
+{
+m_pdata->m_flags = l_flags;
+m_icase = l_flags & regex_constants::icase;
+}
+regbase::flag_type flags()
+{
+return m_pdata->m_flags;
+}
+void flags(regbase::flag_type f)
+{
+m_pdata->m_flags = f;
+if(m_icase != static_cast<bool>(f & regbase::icase))
+{
+m_icase = static_cast<bool>(f & regbase::icase);
+}
+}
+re_syntax_base* append_state(syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
+re_syntax_base* insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s = sizeof(re_syntax_base));
+re_literal* append_literal(charT c);
+re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set);
+re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::false_*);
+re_syntax_base* append_set(const basic_char_set<charT, traits>& char_set, mpl::true_*);
+void finalize(const charT* p1, const charT* p2);
+protected:
+regex_data<charT, traits>*    m_pdata;              // pointer to the basic_regex_data struct we are filling in
+const ::boost::regex_traits_wrapper<traits>&
+m_traits;             // convenience reference to traits class
+re_syntax_base*               m_last_state;         // the last state we added
+bool                          m_icase;              // true for case insensitive matches
+unsigned                      m_repeater_id;        // the state_id of the next repeater
+bool                          m_has_backrefs;       // true if there are actually any backrefs
+unsigned                      m_backrefs;           // bitmask of permitted backrefs
+boost::uintmax_t              m_bad_repeats;        // bitmask of repeats we can't deduce a startmap for;
+typename traits::char_class_type m_word_mask;       // mask used to determine if a character is a word character
+typename traits::char_class_type m_mask_space;      // mask used to determine if a character is a word character
+typename traits::char_class_type m_lower_mask;       // mask used to determine if a character is a lowercase character
+typename traits::char_class_type m_upper_mask;      // mask used to determine if a character is an uppercase character
+typename traits::char_class_type m_alpha_mask;      // mask used to determine if a character is an alphabetic character
+private:
+basic_regex_creator& operator=(const basic_regex_creator&);
+basic_regex_creator(const basic_regex_creator&);
+void fixup_pointers(re_syntax_base* state);
+void create_startmaps(re_syntax_base* state);
+int calculate_backstep(re_syntax_base* state);
+void create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask);
+unsigned get_restart_type(re_syntax_base* state);
+void set_all_masks(unsigned char* bits, unsigned char);
+bool is_bad_repeat(re_syntax_base* pt);
+void set_bad_repeat(re_syntax_base* pt);
+syntax_element_type get_repeat_type(re_syntax_base* state);
+void probe_leading_repeat(re_syntax_base* state);
+};
+template <class charT, class traits>
+basic_regex_creator<charT, traits>::basic_regex_creator(regex_data<charT, traits>* data)
+: m_pdata(data), m_traits(*(data->m_ptraits)), m_last_state(0), m_repeater_id(0), m_has_backrefs(false), m_backrefs(0)
+{
+m_pdata->m_data.clear();
+m_pdata->m_status = ::boost::regex_constants::error_ok;
+static const charT w = 'w';
+static const charT s = 's';
+static const charT l[5] = { 'l', 'o', 'w', 'e', 'r', };
+static const charT u[5] = { 'u', 'p', 'p', 'e', 'r', };
+static const charT a[5] = { 'a', 'l', 'p', 'h', 'a', };
+m_word_mask = m_traits.lookup_classname(&w, &w +1);
+m_mask_space = m_traits.lookup_classname(&s, &s +1);
+m_lower_mask = m_traits.lookup_classname(l, l + 5);
+m_upper_mask = m_traits.lookup_classname(u, u + 5);
+m_alpha_mask = m_traits.lookup_classname(a, a + 5);
+m_pdata->m_word_mask = m_word_mask;
+BOOST_ASSERT(m_word_mask != 0);
+BOOST_ASSERT(m_mask_space != 0);
+BOOST_ASSERT(m_lower_mask != 0);
+BOOST_ASSERT(m_upper_mask != 0);
+BOOST_ASSERT(m_alpha_mask != 0);
+}
+template <class charT, class traits>
+re_syntax_base* basic_regex_creator<charT, traits>::append_state(syntax_element_type t, std::size_t s)
+{
+// if the state is a backref then make a note of it:
+if(t == syntax_element_backref)
+this->m_has_backrefs = true;
+// append a new state, start by aligning our last one:
+m_pdata->m_data.align();
+// set the offset to the next state in our last one:
+if(m_last_state)
+m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
+// now actually extent our data:
+m_last_state = static_cast<re_syntax_base*>(m_pdata->m_data.extend(s));
+// fill in boilerplate options in the new state:
+m_last_state->next.i = 0;
+m_last_state->type = t;
+return m_last_state;
+}
+template <class charT, class traits>
+re_syntax_base* basic_regex_creator<charT, traits>::insert_state(std::ptrdiff_t pos, syntax_element_type t, std::size_t s)
+{
+// append a new state, start by aligning our last one:
+m_pdata->m_data.align();
+// set the offset to the next state in our last one:
+if(m_last_state)
+m_last_state->next.i = m_pdata->m_data.size() - getoffset(m_last_state);
+// remember the last state position:
+std::ptrdiff_t off = getoffset(m_last_state) + s;
+// now actually insert our data:
+re_syntax_base* new_state = static_cast<re_syntax_base*>(m_pdata->m_data.insert(pos, s));
+// fill in boilerplate options in the new state:
+new_state->next.i = s;
+new_state->type = t;
+m_last_state = getaddress(off);
+return new_state;
+}
+template <class charT, class traits>
+re_literal* basic_regex_creator<charT, traits>::append_literal(charT c)
+{
+re_literal* result;
+// start by seeing if we have an existing re_literal we can extend:
+if((0 == m_last_state) || (m_last_state->type != syntax_element_literal))
+{
+// no existing re_literal, create a new one:
+result = static_cast<re_literal*>(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT)));
+result->length = 1;
+*static_cast<charT*>(static_cast<void*>(result+1)) = m_traits.translate(c, m_icase);
+}
+else
+{
+// we have an existing re_literal, extend it:
+std::ptrdiff_t off = getoffset(m_last_state);
+m_pdata->m_data.extend(sizeof(charT));
+m_last_state = result = static_cast<re_literal*>(getaddress(off));
+charT* characters = static_cast<charT*>(static_cast<void*>(result+1));
+characters[result->length] = m_traits.translate(c, m_icase);
+++(result->length);
+}
+return result;
+}
+template <class charT, class traits>
+inline re_syntax_base* basic_regex_creator<charT, traits>::append_set(
+const basic_char_set<charT, traits>& char_set)
+{
+typedef mpl::bool_< (sizeof(charT) == 1) > truth_type;
+return char_set.has_digraphs()
+? append_set(char_set, static_cast<mpl::false_*>(0))
+: append_set(char_set, static_cast<truth_type*>(0));
+}
+template <class charT, class traits>
+re_syntax_base* basic_regex_creator<charT, traits>::append_set(
+const basic_char_set<charT, traits>& char_set, mpl::false_*)
+{
+typedef typename traits::string_type string_type;
+typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
+typedef typename traits::char_class_type mask_type;
+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>)));
+//
+// fill in the basics:
+//
+result->csingles = static_cast<unsigned int>(::boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end()));
+result->cranges = static_cast<unsigned int>(::boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2;
+result->cequivalents = static_cast<unsigned int>(::boost::re_detail::distance(char_set.equivalents_begin(), char_set.equivalents_end()));
+result->cclasses = char_set.classes();
+result->cnclasses = char_set.negated_classes();
+if(flags() & regbase::icase)
+{
+// adjust classes as needed:
+if(((result->cclasses & m_lower_mask) == m_lower_mask) || ((result->cclasses & m_upper_mask) == m_upper_mask))
+result->cclasses |= m_alpha_mask;
+if(((result->cnclasses & m_lower_mask) == m_lower_mask) || ((result->cnclasses & m_upper_mask) == m_upper_mask))
+result->cnclasses |= m_alpha_mask;
+}
+result->isnot = char_set.is_negated();
+result->singleton = !char_set.has_digraphs();
+//
+// remember where the state is for later:
+//
+std::ptrdiff_t offset = getoffset(result);
+//
+// now extend with all the singles:
+//
+item_iterator first, last;
+first = char_set.singles_begin();
+last = char_set.singles_end();
+while(first != last)
+{
+charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (first->second ? 3 : 2)));
+p[0] = m_traits.translate(first->first, m_icase);
+if(first->second)
+{
+p[1] = m_traits.translate(first->second, m_icase);
+p[2] = 0;
+}
+else
+p[1] = 0;
+++first;
+}
+//
+// now extend with all the ranges:
+//
+first = char_set.ranges_begin();
+last = char_set.ranges_end();
+while(first != last)
+{
+// first grab the endpoints of the range:
+digraph<charT> c1 = *first;
+c1.first = this->m_traits.translate(c1.first, this->m_icase);
+c1.second = this->m_traits.translate(c1.second, this->m_icase);
+++first;
+digraph<charT> c2 = *first;
+c2.first = this->m_traits.translate(c2.first, this->m_icase);
+c2.second = this->m_traits.translate(c2.second, this->m_icase);
+++first;
+string_type s1, s2;
+// different actions now depending upon whether collation is turned on:
+if(flags() & regex_constants::collate)
+{
+// we need to transform our range into sort keys:
+#if BOOST_WORKAROUND(__GNUC__, < 3)
+string_type in(3, charT(0));
+in[0] = c1.first;
+in[1] = c1.second;
+s1 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
+in[0] = c2.first;
+in[1] = c2.second;
+s2 = this->m_traits.transform(in.c_str(), (in[1] ? in.c_str()+2 : in.c_str()+1));
+#else
+charT a1[3] = { c1.first, c1.second, charT(0), };
+charT a2[3] = { c2.first, c2.second, charT(0), };
+s1 = this->m_traits.transform(a1, (a1[1] ? a1+2 : a1+1));
+s2 = this->m_traits.transform(a2, (a2[1] ? a2+2 : a2+1));
+#endif
+if(s1.size() == 0)
+s1 = string_type(1, charT(0));
+if(s2.size() == 0)
+s2 = string_type(1, charT(0));
+}
+else
+{
+if(c1.second)
+{
+s1.insert(s1.end(), c1.first);
+s1.insert(s1.end(), c1.second);
+}
+else
+s1 = string_type(1, c1.first);
+if(c2.second)
+{
+s2.insert(s2.end(), c2.first);
+s2.insert(s2.end(), c2.second);
+}
+else
+s2.insert(s2.end(), c2.first);
+}
+if(s1 > s2)
+{
+// Oops error:
+return 0;
+}
+charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s1.size() + s2.size() + 2) ) );
+re_detail::copy(s1.begin(), s1.end(), p);
+p[s1.size()] = charT(0);
+p += s1.size() + 1;
+re_detail::copy(s2.begin(), s2.end(), p);
+p[s2.size()] = charT(0);
+}
+//
+// now process the equivalence classes:
+//
+first = char_set.equivalents_begin();
+last = char_set.equivalents_end();
+while(first != last)
+{
+string_type s;
+if(first->second)
+{
+#if BOOST_WORKAROUND(__GNUC__, < 3)
+string_type in(3, charT(0));
+in[0] = first->first;
+in[1] = first->second;
+s = m_traits.transform_primary(in.c_str(), in.c_str()+2);
+#else
+charT cs[3] = { first->first, first->second, charT(0), };
+s = m_traits.transform_primary(cs, cs+2);
+#endif
+}
+else
+s = m_traits.transform_primary(&first->first, &first->first+1);
+if(s.empty())
+return 0;  // invalid or unsupported equivalence class
+charT* p = static_cast<charT*>(this->m_pdata->m_data.extend(sizeof(charT) * (s.size()+1) ) );
+re_detail::copy(s.begin(), s.end(), p);
+p[s.size()] = charT(0);
+++first;
+}
+//
+// finally reset the address of our last state:
+//
+m_last_state = result = static_cast<re_set_long<mask_type>*>(getaddress(offset));
+return result;
+}
+namespace{
+template<class T>
+inline bool char_less(T t1, T t2)
+{
+return t1 < t2;
+}
+template<>
+inline bool char_less<char>(char t1, char t2)
+{
+return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
+}
+template<>
+inline bool char_less<signed char>(signed char t1, signed char t2)
+{
+return static_cast<unsigned char>(t1) < static_cast<unsigned char>(t2);
+}
+}
+template <class charT, class traits>
+re_syntax_base* basic_regex_creator<charT, traits>::append_set(
+const basic_char_set<charT, traits>& char_set, mpl::true_*)
+{
+typedef typename traits::string_type string_type;
+typedef typename basic_char_set<charT, traits>::list_iterator item_iterator;
+re_set* result = static_cast<re_set*>(append_state(syntax_element_set, sizeof(re_set)));
+bool negate = char_set.is_negated();
+std::memset(result->_map, 0, sizeof(result->_map));
+//
+// handle singles first:
+//
+item_iterator first, last;
+first = char_set.singles_begin();
+last = char_set.singles_end();
+while(first != last)
+{
+for(unsigned int i = 0; i < (1 << CHAR_BIT); ++i)
+{
+if(this->m_traits.translate(static_cast<charT>(i), this->m_icase)
+== this->m_traits.translate(first->first, this->m_icase))
+result->_map[i] = true;
+}
+++first;
+}
+//
+// OK now handle ranges:
+//
+first = char_set.ranges_begin();
+last = char_set.ranges_end();
+while(first != last)
+{
+// first grab the endpoints of the range:
+charT c1 = this->m_traits.translate(first->first, this->m_icase);
+++first;
+charT c2 = this->m_traits.translate(first->first, this->m_icase);
+++first;
+// different actions now depending upon whether collation is turned on:
+if(flags() & regex_constants::collate)
+{
+// we need to transform our range into sort keys:
+charT c3[2] = { c1, charT(0), };
+string_type s1 = this->m_traits.transform(c3, c3+1);
+c3[0] = c2;
+string_type s2 = this->m_traits.transform(c3, c3+1);
+if(s1 > s2)
+{
+// Oops error:
+return 0;
+}
+BOOST_ASSERT(c3[1] == charT(0));
+for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
+{
+c3[0] = static_cast<charT>(i);
+string_type s3 = this->m_traits.transform(c3, c3 +1);
+if((s1 <= s3) && (s3 <= s2))
+result->_map[i] = true;
+}
+}
+else
+{
+if(char_less<charT>(c2, c1))
+{
+// Oops error:
+return 0;
+}
+// everything in range matches:
+std::memset(result->_map + static_cast<unsigned char>(c1), true, 1 + static_cast<unsigned char>(c2) - static_cast<unsigned char>(c1));
+}
+}
+//
+// and now the classes:
+//
+typedef typename traits::char_class_type mask_type;
+mask_type m = char_set.classes();
+if(flags() & regbase::icase)
+{
+// adjust m as needed:
+if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
+m |= m_alpha_mask;
+}
+if(m != 0)
+{
+for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
+{
+if(this->m_traits.isctype(static_cast<charT>(i), m))
+result->_map[i] = true;
+}
+}
+//
+// and now the negated classes:
+//
+m = char_set.negated_classes();
+if(flags() & regbase::icase)
+{
+// adjust m as needed:
+if(((m & m_lower_mask) == m_lower_mask) || ((m & m_upper_mask) == m_upper_mask))
+m |= m_alpha_mask;
+}
+if(m != 0)
+{
+for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
+{
+if(0 == this->m_traits.isctype(static_cast<charT>(i), m))
+result->_map[i] = true;
+}
+}
+//
+// now process the equivalence classes:
+//
+first = char_set.equivalents_begin();
+last = char_set.equivalents_end();
+while(first != last)
+{
+string_type s;
+BOOST_ASSERT(static_cast<charT>(0) == first->second);
+s = m_traits.transform_primary(&first->first, &first->first+1);
+if(s.empty())
+return 0;  // invalid or unsupported equivalence class
+for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
+{
+charT c[2] = { (static_cast<charT>(i)), charT(0), };
+string_type s2 = this->m_traits.transform_primary(c, c+1);
+if(s == s2)
+result->_map[i] = true;
+}
+++first;
+}
+if(negate)
+{
+for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
+{
+result->_map[i] = !(result->_map[i]);
+}
+}
+return result;
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::finalize(const charT* p1, const charT* p2)
+{
+// we've added all the states we need, now finish things off.
+// start by adding a terminating state:
+append_state(syntax_element_match);
+// extend storage to store original expression:
+std::ptrdiff_t len = p2 - p1;
+m_pdata->m_expression_len = len;
+charT* ps = static_cast<charT*>(m_pdata->m_data.extend(sizeof(charT) * (1 + (p2 - p1))));
+m_pdata->m_expression = ps;
+re_detail::copy(p1, p2, ps);
+ps[p2 - p1] = 0;
+// fill in our other data...
+// successful parsing implies a zero status:
+m_pdata->m_status = 0;
+// get the first state of the machine:
+m_pdata->m_first_state = static_cast<re_syntax_base*>(m_pdata->m_data.data());
+// fixup pointers in the machine:
+fixup_pointers(m_pdata->m_first_state);
+// create nested startmaps:
+create_startmaps(m_pdata->m_first_state);
+// create main startmap:
+std::memset(m_pdata->m_startmap, 0, sizeof(m_pdata->m_startmap));
+m_pdata->m_can_be_null = 0;
+m_bad_repeats = 0;
+create_startmap(m_pdata->m_first_state, m_pdata->m_startmap, &(m_pdata->m_can_be_null), mask_all);
+// get the restart type:
+m_pdata->m_restart_type = get_restart_type(m_pdata->m_first_state);
+// optimise a leading repeat if there is one:
+probe_leading_repeat(m_pdata->m_first_state);
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::fixup_pointers(re_syntax_base* state)
+{
+while(state)
+{
+switch(state->type)
+{
+case syntax_element_rep:
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_long_set_rep:
+// set the state_id of this repeat:
+static_cast<re_repeat*>(state)->state_id = m_repeater_id++;
+// fall through:
+case syntax_element_alt:
+std::memset(static_cast<re_alt*>(state)->_map, 0, sizeof(static_cast<re_alt*>(state)->_map));
+static_cast<re_alt*>(state)->can_be_null = 0;
+// fall through:
+case syntax_element_jump:
+static_cast<re_jump*>(state)->alt.p = getaddress(static_cast<re_jump*>(state)->alt.i, state);
+// fall through again:
+default:
+if(state->next.i)
+state->next.p = getaddress(state->next.i, state);
+else
+state->next.p = 0;
+}
+state = state->next.p;
+}
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::create_startmaps(re_syntax_base* state)
+{
+// non-recursive implementation:
+// create the last map in the machine first, so that earlier maps
+// can make use of the result...
+//
+// This was originally a recursive implementation, but that caused stack
+// overflows with complex expressions on small stacks (think COM+).
+// start by saving the case setting:
+bool l_icase = m_icase;
+std::vector<std::pair<bool, re_syntax_base*> > v;
+while(state)
+{
+switch(state->type)
+{
+case syntax_element_toggle_case:
+// we need to track case changes here:
+m_icase = static_cast<re_case*>(state)->icase;
+state = state->next.p;
+continue;
+case syntax_element_alt:
+case syntax_element_rep:
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_long_set_rep:
+// just push the state onto our stack for now:
+v.push_back(std::pair<bool, re_syntax_base*>(m_icase, state));
+state = state->next.p;
+break;
+case syntax_element_backstep:
+// we need to calculate how big the backstep is:
+static_cast<re_brace*>(state)->index
+= this->calculate_backstep(state->next.p);
+if(static_cast<re_brace*>(state)->index < 0)
+{
+// Oops error:
+if(0 == this->m_pdata->m_status) // update the error code if not already set
+this->m_pdata->m_status = boost::regex_constants::error_bad_pattern;
+//
+// clear the expression, we should be empty:
+//
+this->m_pdata->m_expression = 0;
+this->m_pdata->m_expression_len = 0;
+//
+// and throw if required:
+//
+if(0 == (this->flags() & regex_constants::no_except))
+{
+std::string message = this->m_pdata->m_ptraits->error_string(boost::regex_constants::error_bad_pattern);
+boost::regex_error e(message, boost::regex_constants::error_bad_pattern, 0);
+e.raise();
+}
+}
+// fall through:
+default:
+state = state->next.p;
+}
+}
+// now work through our list, building all the maps as we go:
+while(v.size())
+{
+const std::pair<bool, re_syntax_base*>& p = v.back();
+m_icase = p.first;
+state = p.second;
+v.pop_back();
+// Build maps:
+m_bad_repeats = 0;
+create_startmap(state->next.p, static_cast<re_alt*>(state)->_map, &static_cast<re_alt*>(state)->can_be_null, mask_take);
+m_bad_repeats = 0;
+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);
+// adjust the type of the state to allow for faster matching:
+state->type = this->get_repeat_type(state);
+}
+// restore case sensitivity:
+m_icase = l_icase;
+}
+template <class charT, class traits>
+int basic_regex_creator<charT, traits>::calculate_backstep(re_syntax_base* state)
+{
+typedef typename traits::char_class_type mask_type;
+int result = 0;
+while(state)
+{
+switch(state->type)
+{
+case syntax_element_startmark:
+if((static_cast<re_brace*>(state)->index == -1)
+|| (static_cast<re_brace*>(state)->index == -2))
+{
+state = static_cast<re_jump*>(state->next.p)->alt.p->next.p;
+continue;
+}
+else if(static_cast<re_brace*>(state)->index == -3)
+{
+state = state->next.p->next.p;
+continue;
+}
+break;
+case syntax_element_endmark:
+if((static_cast<re_brace*>(state)->index == -1)
+|| (static_cast<re_brace*>(state)->index == -2))
+return result;
+break;
+case syntax_element_literal:
+result += static_cast<re_literal*>(state)->length;
+break;
+case syntax_element_wild:
+case syntax_element_set:
+result += 1;
+break;
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_backref:
+case syntax_element_rep:
+case syntax_element_combining:
+case syntax_element_long_set_rep:
+case syntax_element_backstep:
+{
+re_repeat* rep = static_cast<re_repeat *>(state);
+// adjust the type of the state to allow for faster matching:
+state->type = this->get_repeat_type(state);
+if((state->type == syntax_element_dot_rep)
+|| (state->type == syntax_element_char_rep)
+|| (state->type == syntax_element_short_set_rep))
+{
+if(rep->max != rep->min)
+return -1;
+result += static_cast<int>(rep->min);
+state = rep->alt.p;
+continue;
+}
+else if((state->type == syntax_element_long_set_rep))
+{
+BOOST_ASSERT(rep->next.p->type == syntax_element_long_set);
+if(static_cast<re_set_long<mask_type>*>(rep->next.p)->singleton == 0)
+return -1;
+if(rep->max != rep->min)
+return -1;
+result += static_cast<int>(rep->min);
+state = rep->alt.p;
+continue;
+}
+}
+return -1;
+case syntax_element_long_set:
+if(static_cast<re_set_long<mask_type>*>(state)->singleton == 0)
+return -1;
+result += 1;
+break;
+case syntax_element_jump:
+state = static_cast<re_jump*>(state)->alt.p;
+continue;
+default:
+break;
+}
+state = state->next.p;
+}
+return -1;
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask)
+{
+int not_last_jump = 1;
+// track case sensitivity:
+bool l_icase = m_icase;
+while(state)
+{
+switch(state->type)
+{
+case syntax_element_toggle_case:
+l_icase = static_cast<re_case*>(state)->icase;
+state = state->next.p;
+break;
+case syntax_element_literal:
+{
+// don't set anything in *pnull, set each element in l_map
+// that could match the first character in the literal:
+if(l_map)
+{
+l_map[0] |= mask_init;
+charT first_char = *static_cast<charT*>(static_cast<void*>(static_cast<re_literal*>(state) + 1));
+for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
+{
+if(m_traits.translate(static_cast<charT>(i), l_icase) == first_char)
+l_map[i] |= mask;
+}
+}
+return;
+}
+case syntax_element_end_line:
+{
+// next character must be a line separator (if there is one):
+if(l_map)
+{
+l_map[0] |= mask_init;
+l_map['\n'] |= mask;
+l_map['\r'] |= mask;
+l_map['\f'] |= mask;
+l_map[0x85] |= mask;
+}
+// now figure out if we can match a NULL string at this point:
+if(pnull)
+create_startmap(state->next.p, 0, pnull, mask);
+return;
+}
+case syntax_element_backref:
+// can be null, and any character can match:
+if(pnull)
+*pnull |= mask;
+// fall through:
+case syntax_element_wild:
+{
+// can't be null, any character can match:
+set_all_masks(l_map, mask);
+return;
+}
+case syntax_element_match:
+{
+// must be null, any character can match:
+set_all_masks(l_map, mask);
+if(pnull)
+*pnull |= mask;
+return;
+}
+case syntax_element_word_start:
+{
+// recurse, then AND with all the word characters:
+create_startmap(state->next.p, l_map, pnull, mask);
+if(l_map)
+{
+l_map[0] |= mask_init;
+for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
+{
+if(!m_traits.isctype(static_cast<charT>(i), m_word_mask))
+l_map[i] &= static_cast<unsigned char>(~mask);
+}
+}
+return;
+}
+case syntax_element_word_end:
+{
+// recurse, then AND with all the word characters:
+create_startmap(state->next.p, l_map, pnull, mask);
+if(l_map)
+{
+l_map[0] |= mask_init;
+for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
+{
+if(m_traits.isctype(static_cast<charT>(i), m_word_mask))
+l_map[i] &= static_cast<unsigned char>(~mask);
+}
+}
+return;
+}
+case syntax_element_buffer_end:
+{
+// we *must be null* :
+if(pnull)
+*pnull |= mask;
+return;
+}
+case syntax_element_long_set:
+if(l_map)
+{
+typedef typename traits::char_class_type mask_type;
+if(static_cast<re_set_long<mask_type>*>(state)->singleton)
+{
+l_map[0] |= mask_init;
+for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
+{
+charT c = static_cast<charT>(i);
+if(&c != re_is_set_member(&c, &c + 1, static_cast<re_set_long<mask_type>*>(state), *m_pdata, m_icase))
+l_map[i] |= mask;
+}
+}
+else
+set_all_masks(l_map, mask);
+}
+return;
+case syntax_element_set:
+if(l_map)
+{
+l_map[0] |= mask_init;
+for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i)
+{
+if(static_cast<re_set*>(state)->_map[
+static_cast<unsigned char>(m_traits.translate(static_cast<charT>(i), l_icase))])
+l_map[i] |= mask;
+}
+}
+return;
+case syntax_element_jump:
+// take the jump:
+state = static_cast<re_alt*>(state)->alt.p;
+not_last_jump = -1;
+break;
+case syntax_element_alt:
+case syntax_element_rep:
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_long_set_rep:
+{
+re_alt* rep = static_cast<re_alt*>(state);
+if(rep->_map[0] & mask_init)
+{
+if(l_map)
+{
+// copy previous results:
+l_map[0] |= mask_init;
+for(unsigned int i = 0; i <= UCHAR_MAX; ++i)
+{
+if(rep->_map[i] & mask_any)
+l_map[i] |= mask;
+}
+}
+if(pnull)
+{
+if(rep->can_be_null & mask_any)
+*pnull |= mask;
+}
+}
+else
+{
+// we haven't created a startmap for this alternative yet
+// so take the union of the two options:
+if(is_bad_repeat(state))
+{
+set_all_masks(l_map, mask);
+if(pnull)
+*pnull |= mask;
+return;
+}
+set_bad_repeat(state);
+create_startmap(state->next.p, l_map, pnull, mask);
+if((state->type == syntax_element_alt)
+|| (static_cast<re_repeat*>(state)->min == 0)
+|| (not_last_jump == 0))
+create_startmap(rep->alt.p, l_map, pnull, mask);
+}
+}
+return;
+case syntax_element_soft_buffer_end:
+// match newline or null:
+if(l_map)
+{
+l_map[0] |= mask_init;
+l_map['\n'] |= mask;
+l_map['\r'] |= mask;
+}
+if(pnull)
+*pnull |= mask;
+return;
+case syntax_element_endmark:
+// need to handle independent subs as a special case:
+if(static_cast<re_brace*>(state)->index < 0)
+{
+// can be null, any character can match:
+set_all_masks(l_map, mask);
+if(pnull)
+*pnull |= mask;
+return;
+}
+else
+{
+state = state->next.p;
+break;
+}
+case syntax_element_startmark:
+// need to handle independent subs as a special case:
+if(static_cast<re_brace*>(state)->index == -3)
+{
+state = state->next.p->next.p;
+break;
+}
+// otherwise fall through:
+default:
+state = state->next.p;
+}
+++not_last_jump;
+}
+}
+template <class charT, class traits>
+unsigned basic_regex_creator<charT, traits>::get_restart_type(re_syntax_base* state)
+{
+//
+// find out how the machine starts, so we can optimise the search:
+//
+while(state)
+{
+switch(state->type)
+{
+case syntax_element_startmark:
+case syntax_element_endmark:
+state = state->next.p;
+continue;
+case syntax_element_start_line:
+return regbase::restart_line;
+case syntax_element_word_start:
+return regbase::restart_word;
+case syntax_element_buffer_start:
+return regbase::restart_buf;
+case syntax_element_restart_continue:
+return regbase::restart_continue;
+default:
+state = 0;
+continue;
+}
+}
+return regbase::restart_any;
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::set_all_masks(unsigned char* bits, unsigned char mask)
+{
+//
+// set mask in all of bits elements,
+// if bits[0] has mask_init not set then we can
+// optimise this to a call to memset:
+//
+if(bits)
+{
+if(bits[0] == 0)
+(std::memset)(bits, mask, 1u << CHAR_BIT);
+else
+{
+for(unsigned i = 0; i < (1u << CHAR_BIT); ++i)
+bits[i] |= mask;
+}
+bits[0] |= mask_init;
+}
+}
+template <class charT, class traits>
+bool basic_regex_creator<charT, traits>::is_bad_repeat(re_syntax_base* pt)
+{
+switch(pt->type)
+{
+case syntax_element_rep:
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_long_set_rep:
+{
+unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
+if(state_id > sizeof(m_bad_repeats) * CHAR_BIT)
+return true;  // run out of bits, assume we can't traverse this one.
+static const boost::uintmax_t one = 1uL;
+return m_bad_repeats & (one << state_id);
+}
+default:
+return false;
+}
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::set_bad_repeat(re_syntax_base* pt)
+{
+switch(pt->type)
+{
+case syntax_element_rep:
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_long_set_rep:
+{
+unsigned state_id = static_cast<re_repeat*>(pt)->state_id;
+static const boost::uintmax_t one = 1uL;
+if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT)
+m_bad_repeats |= (one << state_id);
+}
+default:
+break;
+}
+}
+template <class charT, class traits>
+syntax_element_type basic_regex_creator<charT, traits>::get_repeat_type(re_syntax_base* state)
+{
+typedef typename traits::char_class_type mask_type;
+if(state->type == syntax_element_rep)
+{
+// check to see if we are repeating a single state:
+if(state->next.p->next.p->next.p == static_cast<re_alt*>(state)->alt.p)
+{
+switch(state->next.p->type)
+{
+case re_detail::syntax_element_wild:
+return re_detail::syntax_element_dot_rep;
+case re_detail::syntax_element_literal:
+return re_detail::syntax_element_char_rep;
+case re_detail::syntax_element_set:
+return re_detail::syntax_element_short_set_rep;
+case re_detail::syntax_element_long_set:
+if(static_cast<re_detail::re_set_long<mask_type>*>(state->next.p)->singleton)
+return re_detail::syntax_element_long_set_rep;
+break;
+default:
+break;
+}
+}
+}
+return state->type;
+}
+template <class charT, class traits>
+void basic_regex_creator<charT, traits>::probe_leading_repeat(re_syntax_base* state)
+{
+// enumerate our states, and see if we have a leading repeat
+// for which failed search restarts can be optimised;
+do
+{
+switch(state->type)
+{
+case syntax_element_startmark:
+if(static_cast<re_brace*>(state)->index >= 0)
+{
+state = state->next.p;
+continue;
+}
+if((static_cast<re_brace*>(state)->index == -1)
+|| (static_cast<re_brace*>(state)->index == -2))
+{
+// skip past the zero width assertion:
+state = static_cast<const re_jump*>(state->next.p)->alt.p->next.p;
+continue;
+}
+if(static_cast<re_brace*>(state)->index == -3)
+{
+// Have to skip the leading jump state:
+state = state->next.p->next.p;
+continue;
+}
+return;
+case syntax_element_endmark:
+case syntax_element_start_line:
+case syntax_element_end_line:
+case syntax_element_word_boundary:
+case syntax_element_within_word:
+case syntax_element_word_start:
+case syntax_element_word_end:
+case syntax_element_buffer_start:
+case syntax_element_buffer_end:
+case syntax_element_restart_continue:
+state = state->next.p;
+break;
+case syntax_element_dot_rep:
+case syntax_element_char_rep:
+case syntax_element_short_set_rep:
+case syntax_element_long_set_rep:
+if(this->m_has_backrefs == 0)
+static_cast<re_repeat*>(state)->leading = true;
+// fall through:
+default:
+return;
+}
+}while(state);
+}
+} // namespace re_detail
+} // namespace boost
+#ifdef BOOST_MSVC
+#  pragma warning(pop)
+#endif
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable: 4103)
+#endif
+#ifdef BOOST_HAS_ABI_HEADERS
+#  include BOOST_ABI_SUFFIX
+#endif
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+#endif