From 8e761289a2446367267c6c0d9a26e734f0f78306 Mon Sep 17 00:00:00 2001 From: Karen Arutyunov Date: Wed, 16 Dec 2020 20:29:05 +0300 Subject: Get rid of legacy build systems and rename cutl/ to libcutl/ --- .../details/boost/regex/v4/basic_regex_creator.hpp | 1571 -------------------- 1 file changed, 1571 deletions(-) delete mode 100644 cutl/details/boost/regex/v4/basic_regex_creator.hpp (limited to 'cutl/details/boost/regex/v4/basic_regex_creator.hpp') diff --git a/cutl/details/boost/regex/v4/basic_regex_creator.hpp b/cutl/details/boost/regex/v4/basic_regex_creator.hpp deleted file mode 100644 index 375d29b..0000000 --- a/cutl/details/boost/regex/v4/basic_regex_creator.hpp +++ /dev/null @@ -1,1571 +0,0 @@ -/* - * - * 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 - * 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 cutl_details_boost{ - -namespace re_detail{ - -template -struct digraph : public std::pair -{ - digraph() : std::pair(0, 0){} - digraph(charT c1) : std::pair(c1, 0){} - digraph(charT c1, charT c2) : std::pair(c1, c2) - {} -#if !BOOST_WORKAROUND(BOOST_MSVC, < 1300) - digraph(const digraph& d) : std::pair(d.first, d.second){} -#endif - template - digraph(const Seq& s) : std::pair() - { - BOOST_ASSERT(s.size() <= 2); - BOOST_ASSERT(s.size()); - this->first = s[0]; - this->second = (s.size() > 1) ? s[1] : 0; - } -}; - -template -class basic_char_set -{ -public: - typedef digraph digraph_type; - typedef typename traits::string_type string_type; - typedef typename traits::char_class_type m_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(m_type m) - { - m_classes |= m; - m_empty = false; - } - void add_negated_class(m_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::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(); - } - m_type classes()const - { - return m_classes; - } - m_type negated_classes()const - { - return m_negated_classes; - } - bool empty()const - { - return m_empty; - } -private: - std::vector m_singles; // a list of single characters to match - std::vector 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 - m_type m_classes; // character classes to match - m_type m_negated_classes; // negated character classes to match - bool m_empty; // whether we've added anything yet - std::vector m_equivalents; // a list of equivalence classes -}; - -template -class basic_regex_creator -{ -public: - basic_regex_creator(regex_data* 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(addr) - static_cast(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(static_cast(static_cast(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(f & regbase::icase)) - { - m_icase = static_cast(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& char_set); - re_syntax_base* append_set(const basic_char_set& char_set, mpl::false_*); - re_syntax_base* append_set(const basic_char_set& char_set, mpl::true_*); - void finalize(const charT* p1, const charT* p2); -protected: - regex_data* m_pdata; // pointer to the basic_regex_data struct we are filling in - const ::cutl_details_boost::regex_traits_wrapper& - 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 - cutl_details_boost::uintmax_t m_bad_repeats; // bitmask of repeats we can't deduce a startmap for; - bool m_has_recursions; // set when we have recursive expresisons to fixup - std::vector m_recursion_checks; // notes which recursions we've followed while analysing this expression - 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 fixup_recursions(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 -basic_regex_creator::basic_regex_creator(regex_data* 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_has_recursions(false) -{ - m_pdata->m_data.clear(); - m_pdata->m_status = ::cutl_details_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 -re_syntax_base* basic_regex_creator::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(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 -re_syntax_base* basic_regex_creator::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(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 -re_literal* basic_regex_creator::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(append_state(syntax_element_literal, sizeof(re_literal) + sizeof(charT))); - result->length = 1; - *static_cast(static_cast(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(getaddress(off)); - charT* characters = static_cast(static_cast(result+1)); - characters[result->length] = m_traits.translate(c, m_icase); - ++(result->length); - } - return result; -} - -template -inline re_syntax_base* basic_regex_creator::append_set( - const basic_char_set& char_set) -{ - typedef mpl::bool_< (sizeof(charT) == 1) > truth_type; - return char_set.has_digraphs() - ? append_set(char_set, static_cast(0)) - : append_set(char_set, static_cast(0)); -} - -template -re_syntax_base* basic_regex_creator::append_set( - const basic_char_set& char_set, mpl::false_*) -{ - typedef typename traits::string_type string_type; - typedef typename basic_char_set::list_iterator item_iterator; - typedef typename traits::char_class_type m_type; - - re_set_long* result = static_cast*>(append_state(syntax_element_long_set, sizeof(re_set_long))); - // - // fill in the basics: - // - result->csingles = static_cast(::cutl_details_boost::re_detail::distance(char_set.singles_begin(), char_set.singles_end())); - result->cranges = static_cast(::cutl_details_boost::re_detail::distance(char_set.ranges_begin(), char_set.ranges_end())) / 2; - result->cequivalents = static_cast(::cutl_details_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(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 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 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(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(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*>(getaddress(offset)); - return result; -} - -template -inline bool char_less(T t1, T t2) -{ - return t1 < t2; -} -inline bool char_less(char t1, char t2) -{ - return static_cast(t1) < static_cast(t2); -} -inline bool char_less(signed char t1, signed char t2) -{ - return static_cast(t1) < static_cast(t2); -} - -template -re_syntax_base* basic_regex_creator::append_set( - const basic_char_set& char_set, mpl::true_*) -{ - typedef typename traits::string_type string_type; - typedef typename basic_char_set::list_iterator item_iterator; - - re_set* result = static_cast(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(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(i); - string_type s3 = this->m_traits.transform(c3, c3 +1); - if((s1 <= s3) && (s3 <= s2)) - result->_map[i] = true; - } - } - else - { - if(char_less(c2, c1)) - { - // Oops error: - return 0; - } - // everything in range matches: - std::memset(result->_map + static_cast(c1), true, 1 + static_cast(c2) - static_cast(c1)); - } - } - // - // and now the classes: - // - typedef typename traits::char_class_type m_type; - m_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(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(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(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(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 -void basic_regex_creator::finalize(const charT* p1, const charT* p2) -{ - if(this->m_pdata->m_status) - return; - // 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(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(m_pdata->m_data.data()); - // fixup pointers in the machine: - fixup_pointers(m_pdata->m_first_state); - if(m_has_recursions) - { - m_pdata->m_has_recursions = true; - fixup_recursions(m_pdata->m_first_state); - if(this->m_pdata->m_status) - return; - } - else - m_pdata->m_has_recursions = false; - // 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; - if(m_has_recursions) - m_recursion_checks.assign(1 + m_pdata->m_mark_count, false); - 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 -void basic_regex_creator::fixup_pointers(re_syntax_base* state) -{ - while(state) - { - switch(state->type) - { - case syntax_element_recurse: - m_has_recursions = true; - if(state->next.i) - state->next.p = getaddress(state->next.i, state); - else - state->next.p = 0; - break; - 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(state)->state_id = m_repeater_id++; - BOOST_FALLTHROUGH; - case syntax_element_alt: - std::memset(static_cast(state)->_map, 0, sizeof(static_cast(state)->_map)); - static_cast(state)->can_be_null = 0; - BOOST_FALLTHROUGH; - case syntax_element_jump: - static_cast(state)->alt.p = getaddress(static_cast(state)->alt.i, state); - BOOST_FALLTHROUGH; - default: - if(state->next.i) - state->next.p = getaddress(state->next.i, state); - else - state->next.p = 0; - } - state = state->next.p; - } -} - -template -void basic_regex_creator::fixup_recursions(re_syntax_base* state) -{ - re_syntax_base* base = state; - while(state) - { - switch(state->type) - { - case syntax_element_assert_backref: - { - // just check that the index is valid: - int idx = static_cast(state)->index; - if(idx < 0) - { - idx = -idx-1; - if(idx >= 10000) - { - idx = m_pdata->get_id(idx); - if(idx <= 0) - { - // check of sub-expression that doesn't exist: - if(0 == this->m_pdata->m_status) // update the error code if not already set - this->m_pdata->m_status = cutl_details_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 = "Encountered a forward reference to a marked sub-expression that does not exist."; - cutl_details_boost::regex_error e(message, cutl_details_boost::regex_constants::error_bad_pattern, 0); - e.raise(); - } - } - } - } - } - break; - case syntax_element_recurse: - { - bool ok = false; - re_syntax_base* p = base; - std::ptrdiff_t idx = static_cast(state)->alt.i; - if(idx > 10000) - { - // - // There may be more than one capture group with this hash, just do what Perl - // does and recurse to the leftmost: - // - idx = m_pdata->get_id(static_cast(idx)); - } - while(p) - { - if((p->type == syntax_element_startmark) && (static_cast(p)->index == idx)) - { - // - // We've found the target of the recursion, set the jump target: - // - static_cast(state)->alt.p = p; - ok = true; - // - // Now scan the target for nested repeats: - // - p = p->next.p; - int next_rep_id = 0; - while(p) - { - switch(p->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: - next_rep_id = static_cast(p)->state_id; - break; - case syntax_element_endmark: - if(static_cast(p)->index == idx) - next_rep_id = -1; - break; - default: - break; - } - if(next_rep_id) - break; - p = p->next.p; - } - if(next_rep_id > 0) - { - static_cast(state)->state_id = next_rep_id - 1; - } - - break; - } - p = p->next.p; - } - if(!ok) - { - // recursion to sub-expression that doesn't exist: - if(0 == this->m_pdata->m_status) // update the error code if not already set - this->m_pdata->m_status = cutl_details_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 = "Encountered a forward reference to a recursive sub-expression that does not exist."; - cutl_details_boost::regex_error e(message, cutl_details_boost::regex_constants::error_bad_pattern, 0); - e.raise(); - } - } - } - break; - default: - break; - } - state = state->next.p; - } -} - -template -void basic_regex_creator::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 > v; - - while(state) - { - switch(state->type) - { - case syntax_element_toggle_case: - // we need to track case changes here: - m_icase = static_cast(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(m_icase, state)); - state = state->next.p; - break; - case syntax_element_backstep: - // we need to calculate how big the backstep is: - static_cast(state)->index - = this->calculate_backstep(state->next.p); - if(static_cast(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 = cutl_details_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 = "Invalid lookbehind assertion encountered in the regular expression."; - cutl_details_boost::regex_error e(message, cutl_details_boost::regex_constants::error_bad_pattern, 0); - e.raise(); - } - } - BOOST_FALLTHROUGH; - default: - state = state->next.p; - } - } - - // now work through our list, building all the maps as we go: - while(v.size()) - { - // Initialize m_recursion_checks if we need it: - if(m_has_recursions) - m_recursion_checks.assign(1 + m_pdata->m_mark_count, false); - - const std::pair& 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(state)->_map, &static_cast(state)->can_be_null, mask_take); - m_bad_repeats = 0; - - if(m_has_recursions) - m_recursion_checks.assign(1 + m_pdata->m_mark_count, false); - create_startmap(static_cast(state)->alt.p, static_cast(state)->_map, &static_cast(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 -int basic_regex_creator::calculate_backstep(re_syntax_base* state) -{ - typedef typename traits::char_class_type m_type; - int result = 0; - while(state) - { - switch(state->type) - { - case syntax_element_startmark: - if((static_cast(state)->index == -1) - || (static_cast(state)->index == -2)) - { - state = static_cast(state->next.p)->alt.p->next.p; - continue; - } - else if(static_cast(state)->index == -3) - { - state = state->next.p->next.p; - continue; - } - break; - case syntax_element_endmark: - if((static_cast(state)->index == -1) - || (static_cast(state)->index == -2)) - return result; - break; - case syntax_element_literal: - result += static_cast(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(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(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*>(rep->next.p)->singleton == 0) - return -1; - if(rep->max != rep->min) - return -1; - result += static_cast(rep->min); - state = rep->alt.p; - continue; - } - } - return -1; - case syntax_element_long_set: - if(static_cast*>(state)->singleton == 0) - return -1; - result += 1; - break; - case syntax_element_jump: - state = static_cast(state)->alt.p; - continue; - case syntax_element_alt: - { - int r1 = calculate_backstep(state->next.p); - int r2 = calculate_backstep(static_cast(state)->alt.p); - if((r1 < 0) || (r1 != r2)) - return -1; - return result + r1; - } - default: - break; - } - state = state->next.p; - } - return -1; -} - -template -void basic_regex_creator::create_startmap(re_syntax_base* state, unsigned char* l_map, unsigned int* pnull, unsigned char mask) -{ - int not_last_jump = 1; - re_syntax_base* recursion_start = 0; - int recursion_sub = 0; - re_syntax_base* recursion_restart = 0; - - // track case sensitivity: - bool l_icase = m_icase; - - while(state) - { - switch(state->type) - { - case syntax_element_toggle_case: - l_icase = static_cast(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(static_cast(static_cast(state) + 1)); - for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i) - { - if(m_traits.translate(static_cast(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[static_cast('\n')] |= mask; - l_map[static_cast('\r')] |= mask; - l_map[static_cast('\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_recurse: - { - if(state->type == syntax_element_startmark) - recursion_sub = static_cast(state)->index; - else - recursion_sub = 0; - if(m_recursion_checks[recursion_sub]) - { - // Infinite recursion!! - if(0 == this->m_pdata->m_status) // update the error code if not already set - this->m_pdata->m_status = cutl_details_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 = "Encountered an infinite recursion."; - cutl_details_boost::regex_error e(message, cutl_details_boost::regex_constants::error_bad_pattern, 0); - e.raise(); - } - } - else if(recursion_start == 0) - { - recursion_start = state; - recursion_restart = state->next.p; - state = static_cast(state)->alt.p; - m_recursion_checks[recursion_sub] = true; - break; - } - m_recursion_checks[recursion_sub] = true; - // can't handle nested recursion here... - BOOST_FALLTHROUGH; - } - case syntax_element_backref: - // can be null, and any character can match: - if(pnull) - *pnull |= mask; - BOOST_FALLTHROUGH; - 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(i), m_word_mask)) - l_map[i] &= static_cast(~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(i), m_word_mask)) - l_map[i] &= static_cast(~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 m_type; - if(static_cast*>(state)->singleton) - { - l_map[0] |= mask_init; - for(unsigned int i = 0; i < (1u << CHAR_BIT); ++i) - { - charT c = static_cast(i); - if(&c != re_is_set_member(&c, &c + 1, static_cast*>(state), *m_pdata, l_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(state)->_map[ - static_cast(m_traits.translate(static_cast(i), l_icase))]) - l_map[i] |= mask; - } - } - return; - case syntax_element_jump: - // take the jump: - state = static_cast(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(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(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[static_cast('\n')] |= mask; - l_map[static_cast('\r')] |= mask; - } - if(pnull) - *pnull |= mask; - return; - case syntax_element_endmark: - // need to handle independent subs as a special case: - if(static_cast(state)->index < 0) - { - // can be null, any character can match: - set_all_masks(l_map, mask); - if(pnull) - *pnull |= mask; - return; - } - else if(recursion_start && (recursion_sub != 0) && (recursion_sub == static_cast(state)->index)) - { - // recursion termination: - recursion_start = 0; - state = recursion_restart; - break; - } - - // - // Normally we just go to the next state... but if this sub-expression is - // the target of a recursion, then we might be ending a recursion, in which - // case we should check whatever follows that recursion, as well as whatever - // follows this state: - // - if(m_pdata->m_has_recursions && static_cast(state)->index) - { - bool ok = false; - re_syntax_base* p = m_pdata->m_first_state; - while(p) - { - if(p->type == syntax_element_recurse) - { - re_brace* p2 = static_cast(static_cast(p)->alt.p); - if((p2->type == syntax_element_startmark) && (p2->index == static_cast(state)->index)) - { - ok = true; - break; - } - } - p = p->next.p; - } - if(ok) - { - create_startmap(p->next.p, l_map, pnull, mask); - } - } - state = state->next.p; - break; - - case syntax_element_startmark: - // need to handle independent subs as a special case: - if(static_cast(state)->index == -3) - { - state = state->next.p->next.p; - break; - } - BOOST_FALLTHROUGH; - default: - state = state->next.p; - } - ++not_last_jump; - } -} - -template -unsigned basic_regex_creator::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 -void basic_regex_creator::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 -bool basic_regex_creator::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(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 cutl_details_boost::uintmax_t one = 1uL; - return m_bad_repeats & (one << state_id); - } - default: - return false; - } -} - -template -void basic_regex_creator::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(pt)->state_id; - static const cutl_details_boost::uintmax_t one = 1uL; - if(state_id <= sizeof(m_bad_repeats) * CHAR_BIT) - m_bad_repeats |= (one << state_id); - } - break; - default: - break; - } -} - -template -syntax_element_type basic_regex_creator::get_repeat_type(re_syntax_base* state) -{ - typedef typename traits::char_class_type m_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(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*>(state->next.p)->singleton) - return re_detail::syntax_element_long_set_rep; - break; - default: - break; - } - } - } - return state->type; -} - -template -void basic_regex_creator::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(state)->index >= 0) - { - state = state->next.p; - continue; - } - if((static_cast(state)->index == -1) - || (static_cast(state)->index == -2)) - { - // skip past the zero width assertion: - state = static_cast(state->next.p)->alt.p->next.p; - continue; - } - if(static_cast(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(state)->leading = true; - BOOST_FALLTHROUGH; - default: - return; - } - }while(state); -} - - -} // namespace re_detail - -} // namespace cutl_details_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 - -- cgit v1.1