diff options
Diffstat (limited to 'libbuild2/script/regex.hxx')
| -rw-r--r-- | libbuild2/script/regex.hxx | 678 |
1 files changed, 678 insertions, 0 deletions
diff --git a/libbuild2/script/regex.hxx b/libbuild2/script/regex.hxx new file mode 100644 index 0000000..30d3363 --- /dev/null +++ b/libbuild2/script/regex.hxx @@ -0,0 +1,678 @@ +// file : libbuild2/script/regex.hxx -*- C++ -*- +// license : MIT; see accompanying LICENSE file + +#ifndef LIBBUILD2_SCRIPT_REGEX_HXX +#define LIBBUILD2_SCRIPT_REGEX_HXX + +#include <list> +#include <regex> +#include <locale> +#include <string> // basic_string +#include <type_traits> // make_unsigned, enable_if, is_* +#include <unordered_set> + +#include <libbuild2/types.hxx> +#include <libbuild2/utility.hxx> + +namespace build2 +{ + namespace script + { + namespace regex + { + using char_string = std::basic_string<char>; + + enum class char_flags: uint16_t + { + icase = 0x1, // Case-insensitive match. + idot = 0x2, // Invert '.' escaping. + + none = 0 + }; + + // Restricts valid standard flags to just {icase}, extends with custom + // flags {idot}. + // + class char_regex: public std::basic_regex<char> + { + public: + using base_type = std::basic_regex<char>; + + char_regex (const char_string&, char_flags = char_flags::none); + }; + + // Newlines are line separators and are not part of the line: + // + // line<newline>line<newline> + // + // Specifically, this means that a customary trailing newline creates a + // trailing blank line. + // + // All characters can inter-compare (though there cannot be regex + // characters in the output, only in line_regex). + // + // Note that we assume that line_regex and the input to regex_match() + // use the same pool. + // + struct line_pool + { + // Note that we assume the pool can be moved without invalidating + // pointers to any already pooled entities. + // + std::unordered_set<char_string> strings; + std::list<char_regex> regexes; + }; + + enum class line_type + { + special, + literal, + regex + }; + + struct line_char + { + // Steal last two bits from the pointer to store the type. + // + private: + std::uintptr_t data_; + + public: + line_type + type () const {return static_cast<line_type> (data_ & 0x3);} + + int + special () const + { + // Stored as (shifted) int16_t. Perform steps reversed to those + // that are described in the comment for the corresponding ctor. + // Note that the intermediate cast to uint16_t is required to + // portably preserve the -1 special character. + // + return static_cast<int16_t> (static_cast<uint16_t> (data_ >> 2)); + } + + const char_string* + literal () const + { + // Note that 2 rightmost bits are used for packaging line_char + // type. Read the comment for the corresponding ctor for details. + // + return reinterpret_cast<const char_string*> ( + data_ & ~std::uintptr_t (0x3)); + } + + const char_regex* + regex () const + { + // Note that 2 rightmost bits are used for packaging line_char + // type. Read the comment for the corresponding ctor for details. + // + return reinterpret_cast<const char_regex*> ( + data_ & ~std::uintptr_t (0x3)); + } + + static const line_char nul; + static const line_char eof; + + // Note: creates an uninitialized value. + // + line_char () = default; + + // Create a special character. The argument value must be one of the + // following ones: + // + // 0 (nul character) + // -1 (EOF) + // [()|.*+?{}\0123456789,=!] (excluding []) + // + // Note that the constructor is implicit to allow basic_regex to + // implicitly construct line_chars from special char literals (in + // particular libstdc++ appends them to an internal line_string). + // + // Also note that we extend the valid characters set (see above) with + // 'p', 'n' (used by libstdc++ for positive/negative look-ahead + // tokens representation), and '\n', '\r', u'\u2028', u'\u2029' (used + // by libstdc++ for newline/newparagraph matching). + // + line_char (int); + + // Create a literal character. + // + // Don't copy string if already pooled. + // + explicit + line_char (const char_string&, line_pool&); + + explicit + line_char (char_string&&, line_pool&); + + explicit + line_char (const char_string* s) // Assume already pooled. + // + // Steal two bits from the pointer to package line_char type. + // Assume (and statically assert) that char_string address is a + // multiple of four. + // + : data_ (reinterpret_cast <std::uintptr_t> (s) | + static_cast <std::uintptr_t> (line_type::literal)) {} + + // Create a regex character. + // + explicit + line_char (char_regex, line_pool&); + + explicit + line_char (const char_regex* r) // Assume already pooled. + // + // Steal two bits from the pointer to package line_char type. + // Assume (and statically assert) that char_regex address is a + // multiple of four. + // + : data_ (reinterpret_cast <std::uintptr_t> (r) | + static_cast <std::uintptr_t> (line_type::regex)) {} + + // Provide basic_regex with the ability to use line_char in a context + // where a char value is expected (e.g., as a function argument). + // + // libstdc++ seems to cast special line_chars only (and such a + // conversion is meanigfull). + // + // msvcrt casts line_chars of arbitrary types instead. The only + // reasonable strategy is to return a value that differs from any + // other that can be encountered in a regex expression and so will + // unlikelly be misinterpreted. + // + operator char () const + { + return type () == line_type::special ? special () : '\a'; // BELL. + } + + // Return true if the character is a syntax (special) one. + // + static bool + syntax (char); + + // Provide basic_regex (such as from msvcrt) with the ability to + // explicitly cast line_chars to implementation-specific numeric + // types (enums, msvcrt's _Uelem, etc). + // + template <typename T> + explicit + operator T () const + { + assert (type () == line_type::special); + return static_cast<T> (special ()); + } + }; + + // Perform "deep" characters comparison (for example match literal + // character with a regex character), rather than just compare them + // literally. At least one argument must be of a type other than regex + // as there is no operator==() defined to compare regexes. Characters + // of the literal type must share the same pool (strings are compared + // by pointers not by values). + // + bool + operator== (const line_char&, const line_char&); + + // Return false if arguments are equal (operator==() returns true). + // Otherwise if types are different return the value implying that + // special < literal < regex. If types are special or literal return + // the result of the respective characters or strings comparison. At + // least one argument must be of a type other than regex as there is no + // operator<() defined to compare regexes. + // + // While not very natural operation for the class we have, we have to + // provide some meaningfull semantics for such a comparison as it is + // required by the char_traits<line_char> specialization. While we + // could provide it right in that specialization, let's keep it here + // for basic_regex implementations that potentially can compare + // line_chars as they compare them with expressions of other types (see + // below). + // + bool + operator< (const line_char&, const line_char&); + + inline bool + operator!= (const line_char& l, const line_char& r) + { + return !(l == r); + } + + inline bool + operator<= (const line_char& l, const line_char& r) + { + return l < r || l == r; + } + + // Provide basic_regex (such as from msvcrt) with the ability to + // compare line_char to a value of an integral or + // implementation-specific enum type. In the absense of the following + // template operators, such a comparisons would be ambigious for + // integral types (given that there are implicit conversions + // int->line_char and line_char->char) and impossible for enums. + // + // Note that these == and < operators can succeed only for a line_char + // of the special type. For other types they always return false. That + // in particular leads to the following case: + // + // (lc != c) != (lc < c || c < lc). + // + // Note that we can not assert line_char is of the special type as + // basic_regex (such as from libc++) may need the ability to check if + // arbitrary line_char belongs to some special characters range (like + // ['0', '9']). + // + template <typename T> + struct line_char_cmp + : public std::enable_if<std::is_integral<T>::value || + (std::is_enum<T>::value && + !std::is_same<T, char_flags>::value)> {}; + + template <typename T, typename = typename line_char_cmp<T>::type> + bool + operator== (const line_char& l, const T& r) + { + return l.type () == line_type::special && + static_cast<T> (l.special ()) == r; + } + + template <typename T, typename = typename line_char_cmp<T>::type> + bool + operator== (const T& l, const line_char& r) + { + return r.type () == line_type::special && + static_cast<T> (r.special ()) == l; + } + + template <typename T, typename = typename line_char_cmp<T>::type> + bool + operator!= (const line_char& l, const T& r) + { + return !(l == r); + } + + template <typename T, typename = typename line_char_cmp<T>::type> + bool + operator!= (const T& l, const line_char& r) + { + return !(l == r); + } + + template <typename T, typename = typename line_char_cmp<T>::type> + bool + operator< (const line_char& l, const T& r) + { + return l.type () == line_type::special && + static_cast<T> (l.special ()) < r; + } + + template <typename T, typename = typename line_char_cmp<T>::type> + bool + operator< (const T& l, const line_char& r) + { + return r.type () == line_type::special && + l < static_cast<T> (r.special ()); + } + + template <typename T, typename = typename line_char_cmp<T>::type> + inline bool + operator<= (const line_char& l, const T& r) + { + return l < r || l == r; + } + + template <typename T, typename = typename line_char_cmp<T>::type> + inline bool + operator<= (const T& l, const line_char& r) + { + return l < r || l == r; + } + + using line_string = std::basic_string<line_char>; + + // Locale that has ctype<line_char> facet installed. Used in the + // regex_traits<line_char> specialization (see below). + // + class line_char_locale: public std::locale + { + public: + // Create a copy of the global C++ locale. + // + line_char_locale (); + }; + + // Initialize the script regex global state. Should be called once + // prior to creating objects of types from this namespace. Note: not + // thread-safe. + // + void + init (); + } + } +} + +// Standard template specializations for line_char that are required for the +// basic_regex<line_char> instantiation. +// +namespace std +{ + template <> + class char_traits<build2::script::regex::line_char> + { + public: + using char_type = build2::script::regex::line_char; + using int_type = char_type; + using off_type = char_traits<char>::off_type; + using pos_type = char_traits<char>::pos_type; + using state_type = char_traits<char>::state_type; + + static void + assign (char_type& c1, const char_type& c2) {c1 = c2;} + + static char_type* + assign (char_type*, size_t, char_type); + + // Note that eq() and lt() are not constexpr (as required by C++11) + // because == and < operators for char_type are not constexpr. + // + static bool + eq (const char_type& l, const char_type& r) {return l == r;} + + static bool + lt (const char_type& l, const char_type& r) {return l < r;} + + static char_type* + move (char_type*, const char_type*, size_t); + + static char_type* + copy (char_type*, const char_type*, size_t); + + static int + compare (const char_type*, const char_type*, size_t); + + static size_t + length (const char_type*); + + static const char_type* + find (const char_type*, size_t, const char_type&); + + static constexpr char_type + to_char_type (const int_type& c) {return c;} + + static constexpr int_type + to_int_type (const char_type& c) {return int_type (c);} + + // Note that the following functions are not constexpr (as required by + // C++11) because their return expressions are not constexpr. + // + static bool + eq_int_type (const int_type& l, const int_type& r) {return l == r;} + + static int_type eof () {return char_type::eof;} + + static int_type + not_eof (const int_type& c) + { + return c != char_type::eof ? c : char_type::nul; + } + }; + + // ctype<> must be derived from both ctype_base and locale::facet (the later + // supports ref-counting used by the std::locale implementation internally). + // + // msvcrt for some reason also derives ctype_base from locale::facet which + // produces "already a base-class" warning and effectivelly breaks the + // reference counting. So we derive from ctype_base only in this case. + // + template <> + class ctype<build2::script::regex::line_char>: public ctype_base +#if !defined(_MSC_VER) || _MSC_VER >= 2000 + , public locale::facet +#endif + { + // Used by the implementation only. + // + using line_type = build2::script::regex::line_type; + + public: + using char_type = build2::script::regex::line_char; + + static locale::id id; + +#if !defined(_MSC_VER) || _MSC_VER >= 2000 + explicit + ctype (size_t refs = 0): locale::facet (refs) {} +#else + explicit + ctype (size_t refs = 0): ctype_base (refs) {} +#endif + + // While unnecessary, let's keep for completeness. + // + virtual + ~ctype () override = default; + + // The C++ standard requires the following functions to call their virtual + // (protected) do_*() counterparts that provide the real implementations. + // The only purpose for this indirection is to provide a user with the + // ability to customize existing (standard) ctype facets. As we do not + // provide such an ability, for simplicity we will omit the do_*() + // functions and provide the implementations directly. This should be safe + // as nobody except us could call those protected functions. + // + bool + is (mask m, char_type c) const + { + return m == + (c.type () == line_type::special && c.special () >= 0 && + build2::digit (static_cast<char> (c.special ())) + ? digit + : 0); + } + + const char_type* + is (const char_type*, const char_type*, mask*) const; + + const char_type* + scan_is (mask, const char_type*, const char_type*) const; + + const char_type* + scan_not (mask, const char_type*, const char_type*) const; + + char_type + toupper (char_type c) const {return c;} + + const char_type* + toupper (char_type*, const char_type* e) const {return e;} + + char_type + tolower (char_type c) const {return c;} + + const char_type* + tolower (char_type*, const char_type* e) const {return e;} + + char_type + widen (char c) const {return char_type (c);} + + const char* + widen (const char*, const char*, char_type*) const; + + char + narrow (char_type c, char def) const + { + return c.type () == line_type::special ? c.special () : def; + } + + const char_type* + narrow (const char_type*, const char_type*, char, char*) const; + }; + + // Note: the current application locale must be POSIX. Otherwise the + // behavior is undefined. + // + template <> + class regex_traits<build2::script::regex::line_char> + { + public: + using char_type = build2::script::regex::line_char; + using string_type = build2::script::regex::line_string; + using locale_type = build2::script::regex::line_char_locale; + using char_class_type = regex_traits<char>::char_class_type; + + // Workaround for msvcrt bugs. For some reason it assumes such a members + // to be present in a regex_traits specialization. + // +#if defined(_MSC_VER) && _MSC_VER < 2000 + static const ctype_base::mask _Ch_upper = ctype_base::upper; + static const ctype_base::mask _Ch_alpha = ctype_base::alpha; + + // Unsigned numeric type. msvcrt normally casts characters to this type + // for comparing with some numeric values or for calculating an index in + // some bit array. Luckily that all relates to the character class + // handling that we don't support. + // + using _Uelem = unsigned int; +#endif + + regex_traits () = default; // Unnecessary but let's keep for completeness. + + static size_t + length (const char_type* p) {return string_type::traits_type::length (p);} + + char_type + translate (char_type c) const {return c;} + + // Case-insensitive matching is not supported by line_regex. So there is no + // reason for the function to be called. + // + char_type + translate_nocase (char_type c) const {assert (false); return c;} + + // Return a sort-key - the exact copy of [b, e). + // + template <typename I> + string_type + transform (I b, I e) const {return string_type (b, e);} + + // Return a case-insensitive sort-key. Case-insensitive matching is not + // supported by line_regex. So there is no reason for the function to be + // called. + // + template <typename I> + string_type + transform_primary (I b, I e) const + { + assert (false); + return string_type (b, e); + } + + // POSIX regex grammar and collating elements (e.g., [.tilde.]) in + // particular are not supported. So there is no reason for the function to + // be called. + // + template <typename I> + string_type + lookup_collatename (I, I) const {assert (false); return string_type ();} + + // Character classes (e.g., [:lower:]) are not supported. So there is no + // reason for the function to be called. + // + template <typename I> + char_class_type + lookup_classname (I, I, bool = false) const + { + assert (false); + return char_class_type (); + } + + // Return false as we don't support character classes (e.g., [:lower:]). + // + bool + isctype (char_type, char_class_type) const {return false;} + + int + value (char_type, int) const; + + // Return the locale passed as an argument as we do not expect anything + // other than POSIX locale, that we also assume to be imbued by default. + // + locale_type + imbue (locale_type l) {return l;} + + locale_type + getloc () const {return locale_type ();} + }; + + // We assume line_char to be an unsigned type and express that with the + // following specialization used by basic_regex implementations. + // + // libstdc++ defines unsigned CharT type (regex_traits template parameter) + // to use as an index in some internal cache regardless if the cache is used + // for this specialization (and the cache is used only if CharT is char). + // + template <> + struct make_unsigned<build2::script::regex::line_char> + { + using type = build2::script::regex::line_char; + }; + + // When used with libc++ the linker complains that it can't find + // __match_any_but_newline<line_char>::__exec() function. The problem is + // that the function is only specialized for char and wchar_t + // (LLVM bug #31409). As line_char has no notion of the newline character we + // specialize the class template to behave as the __match_any<line_char> + // instantiation does (that luckily has all the functions in place). + // +#if defined(_LIBCPP_VERSION) && _LIBCPP_VERSION <= 9000 + template <> + class __match_any_but_newline<build2::script::regex::line_char> + : public __match_any<build2::script::regex::line_char> + { + public: + using base = __match_any<build2::script::regex::line_char>; + using base::base; + }; +#endif +} + +namespace build2 +{ + namespace script + { + namespace regex + { + class line_regex: public std::basic_regex<line_char> + { + public: + using base_type = std::basic_regex<line_char>; + + using base_type::base_type; + + line_regex () = default; + + // Move string regex together with the pool used to create it. + // + line_regex (line_string&& s, line_pool&& p) + // No move-string ctor for base_type, so emulate it. + // + : base_type (s), pool (move (p)) {s.clear ();} + + // Move constuctible/assignable-only type. + // + line_regex (line_regex&&) = default; + line_regex (const line_regex&) = delete; + line_regex& operator= (line_regex&&) = default; + line_regex& operator= (const line_regex&) = delete; + + public: + line_pool pool; + }; + } + } +} + +#include <libbuild2/script/regex.ixx> + +#endif // LIBBUILD2_SCRIPT_REGEX_HXX |