This is an automated email from the ASF dual-hosted git repository. szaszm pushed a commit to branch main in repository https://gitbox.apache.org/repos/asf/nifi-minifi-cpp.git
commit 7e56a79efd56967ff0962308bcec96546355c7f5 Author: Adam Debreceni <[email protected]> AuthorDate: Thu Sep 22 15:45:43 2022 +0200 MINIFICPP-1903 Refactor utils::Regex ... to take advantage of more optimal regex methods on supported platforms Closes #1387 Signed-off-by: Marton Szasz <[email protected]> --- libminifi/include/utils/RegexUtils.h | 109 +++++++-------- libminifi/src/utils/RegexUtils.cpp | 239 ++++++++++++++++++++++++-------- libminifi/test/unit/RegexUtilsTests.cpp | 52 +++++++ 3 files changed, 284 insertions(+), 116 deletions(-) diff --git a/libminifi/include/utils/RegexUtils.h b/libminifi/include/utils/RegexUtils.h index d09c4e793..391486818 100644 --- a/libminifi/include/utils/RegexUtils.h +++ b/libminifi/include/utils/RegexUtils.h @@ -22,6 +22,7 @@ #include <string_view> #include <vector> #include <cstddef> +#include <utility> // There is a bug in std::regex implementation of libstdc++ which causes stack overflow on long matches: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86164 // Due to this bug we should use regex.h for regex searches if libstdc++ is used until a fix is released. @@ -38,84 +39,66 @@ class Regex; #ifdef NO_MORE_REGFREEE using SMatch = std::smatch; +using CMatch = std::cmatch; +using SVMatch = std::match_results<std::string_view::const_iterator>; #else +class SMatch; +using SVMatch = SMatch; +using CMatch = SMatch; + class SMatch { struct Regmatch; - struct SuffixWrapper; public: - struct Iterator { - using iterator_category = std::forward_iterator_tag; - using difference_type = std::ptrdiff_t; - using value_type = Regmatch; - using pointer = value_type*; - using reference = value_type&; - - Iterator() : regmatch_(nullptr) { - } - - explicit Iterator(Regmatch* regmatch) - : regmatch_(regmatch) { - } - - reference operator*() const { return *regmatch_; } - pointer operator->() { return regmatch_; } - - Iterator& operator++() { regmatch_++; return *this; } - Iterator operator++(int) { Iterator tmp = *this; ++(*this); return tmp; } + SMatch() = default; + SMatch(const SMatch&); + SMatch(SMatch&&); + SMatch& operator=(const SMatch&); + SMatch& operator=(SMatch&&); - friend bool operator== (const Iterator& a, const Iterator& b) { return a.regmatch_ == b.regmatch_; } - friend bool operator!= (const Iterator& a, const Iterator& b) { return a.regmatch_ != b.regmatch_; } - - private: - pointer regmatch_; - }; - - SuffixWrapper suffix() const; + const Regmatch& suffix() const; const Regmatch& operator[](std::size_t index) const; - Iterator begin() { return Iterator(&matches_[0]); } - Iterator end() { return Iterator(&matches_[matches_.size()]); } + auto begin() { return matches_.begin(); } + auto end() { return matches_.end(); } std::size_t size() const; + bool empty() const; bool ready() const; std::size_t position(std::size_t index) const; std::size_t length(std::size_t index) const; private: - struct Regmatch { + struct Regmatch : std::pair<std::string::const_iterator, std::string::const_iterator> { + Regmatch(bool matched, std::string::const_iterator begin, std::string::const_iterator end): pair{begin, end}, matched(matched) {} + operator std::string() const { return str(); } std::string str() const { - if (match.rm_so == -1) { + if (!matched) { return ""; } - return std::string(string.begin() + match.rm_so, string.begin() + match.rm_eo); - } - - regmatch_t match; - std::string_view string; - }; - - struct SuffixWrapper { - operator std::string() const { - return str(); + return std::string(first, second); } - std::string str() const { - return suffix; + std::size_t length() const { + return std::distance(first, second); } - std::string suffix; + bool matched; }; - void clear(); + void reset(std::string str); + bool ready_{false}; std::vector<Regmatch> matches_; std::string string_; + Regmatch unmatched_{false, string_.end(), string_.end()}; + Regmatch suffix_{unmatched_}; + + friend bool regexMatch(const std::string& str, SMatch& match, const Regex& regex); + friend bool regexSearch(const std::string& str, SMatch& match, const Regex& regex); - friend bool regexMatch(const std::string& string, SMatch& match, const Regex& regex); - friend bool regexSearch(const std::string& string, SMatch& match, const Regex& regex); friend utils::SMatch getLastRegexMatch(const std::string& string, const utils::Regex& pattern); }; #endif @@ -150,18 +133,32 @@ class Regex { int regex_mode_; #endif - friend bool regexMatch(const std::string &string, const Regex& regex); - friend bool regexMatch(const std::string &string, SMatch& match, const Regex& regex); - friend bool regexSearch(const std::string &string, const Regex& regex); - friend bool regexSearch(const std::string &string, SMatch& match, const Regex& regex); + friend bool regexMatch(const char* str, CMatch& match, const Regex& regex); + friend bool regexSearch(const char* str, CMatch& match, const Regex& regex); + + friend bool regexMatch(const std::string_view& str, SVMatch& match, const Regex& regex); + friend bool regexSearch(const std::string_view& str, SVMatch& match, const Regex& regex); + + friend bool regexMatch(const std::string& str, SMatch& match, const Regex& regex); + friend bool regexSearch(const std::string& str, SMatch& match, const Regex& regex); + friend SMatch getLastRegexMatch(const std::string& string, const utils::Regex& regex); }; -bool regexMatch(const std::string &string, const Regex& regex); -bool regexMatch(const std::string &string, SMatch& match, const Regex& regex); +bool regexMatch(const char* str, const Regex& regex); +bool regexMatch(const char* str, CMatch& match, const Regex& regex); +bool regexSearch(const char* str, const Regex& regex); +bool regexSearch(const char* str, CMatch& match, const Regex& regex); + +bool regexMatch(const std::string_view& str, const Regex& regex); +bool regexMatch(const std::string_view& str, SVMatch& match, const Regex& regex); +bool regexSearch(const std::string_view& str, const Regex& regex); +bool regexSearch(const std::string_view& str, SVMatch& match, const Regex& regex); -bool regexSearch(const std::string &string, const Regex& regex); -bool regexSearch(const std::string &string, SMatch& match, const Regex& regex); +bool regexMatch(const std::string& str, const Regex& regex); +bool regexMatch(const std::string& str, SMatch& match, const Regex& regex); +bool regexSearch(const std::string& str, const Regex& regex); +bool regexSearch(const std::string& str, SMatch& match, const Regex& regex); /** * Returns the last match of a regular expression within the given string diff --git a/libminifi/src/utils/RegexUtils.cpp b/libminifi/src/utils/RegexUtils.cpp index 8374fd230..e8de1c396 100644 --- a/libminifi/src/utils/RegexUtils.cpp +++ b/libminifi/src/utils/RegexUtils.cpp @@ -23,57 +23,84 @@ #include "Exception.h" +namespace org::apache::nifi::minifi::utils { + #ifndef NO_MORE_REGFREEE -namespace { -std::size_t getMaxGroupCountOfRegex(const std::string& regex) { - return std::count(regex.begin(), regex.end(), '(') + 1; +SMatch::SMatch(const SMatch& other) { + *this = other; } -} // namespace -#endif - -namespace org::apache::nifi::minifi::utils { +SMatch::SMatch(SMatch&& other) { + *this = std::move(other); +} -#ifndef NO_MORE_REGFREEE -SMatch::SuffixWrapper SMatch::suffix() const { - if ((size_t) matches_[0].match.rm_eo >= string_.size()) { - return SuffixWrapper{std::string()}; - } else { - return SuffixWrapper{string_.substr(matches_[0].match.rm_eo)}; +SMatch& SMatch::operator=(const SMatch& other) { + if (this == &other) { + return *this; + } + reset(other.string_); + matches_.reserve(other.matches_.size()); + ready_ = other.ready_; + for (const auto& sub_match : other.matches_) { + size_t begin_off = gsl::narrow<size_t>(std::distance(other.string_.begin(), sub_match.first)); + size_t end_off = gsl::narrow<size_t>(std::distance(other.string_.begin(), sub_match.second)); + matches_.push_back(Regmatch{sub_match.matched, string_.begin() + begin_off, string_.begin() + end_off}); } + return *this; +} + +SMatch& SMatch::operator=(SMatch&& other) { + // trigger the copy assignment, we could optimize this (by moving the string/matches) + // but we would need to maintain a separate offsets vector, as after the move the original + // sub_matches' iterators are invalidated, if this turns out to be a performance bottleneck + // revisit this + return *this = other; +} + +const SMatch::Regmatch& SMatch::suffix() const { + return suffix_; } const SMatch::Regmatch& SMatch::operator[](std::size_t index) const { + if (index >= matches_.size()) { + return unmatched_; + } return matches_[index]; } std::size_t SMatch::size() const { - std::size_t count = 0; - for (const auto &m : matches_) { - if (m.match.rm_so == -1) { - break; - } - ++count; - } - return count; + return matches_.size(); +} + +bool SMatch::empty() const { + return size() == 0; } bool SMatch::ready() const { - return !matches_.empty(); + return ready_; } std::size_t SMatch::position(std::size_t index) const { - return matches_.at(index).match.rm_so; + if (index >= matches_.size()) { + return std::distance(string_.begin(), unmatched_.first); + } + return std::distance(string_.begin(), matches_[index].first); } std::size_t SMatch::length(std::size_t index) const { - return matches_.at(index).match.rm_eo - matches_.at(index).match.rm_so; + if (index >= matches_.size()) { + return std::distance(unmatched_.first, unmatched_.second); + } + return std::distance(matches_[index].first, matches_[index].second); } -void SMatch::clear() { +void SMatch::reset(std::string str) { matches_.clear(); - string_.clear(); + string_ = std::move(str); + unmatched_ = Regmatch{false, string_.end(), string_.end()}; + suffix_ = unmatched_; + ready_ = false; } #endif @@ -197,65 +224,131 @@ void Regex::compileRegex(regex_t& regex, const std::string& regex_string) const } #endif -bool regexSearch(const std::string &string, const Regex& regex) { +bool regexMatch(const char* str, const Regex& regex) { + CMatch match; + return regexMatch(str, match, regex); +} + +bool regexMatch(const std::string_view& str, const Regex& regex) { + SVMatch match; + return regexMatch(str, match, regex); +} + +bool regexMatch(const std::string& str, const Regex& regex) { + SMatch match; + return regexMatch(str, match, regex); +} + +bool regexMatch(const char* str, CMatch& match, const Regex& regex) { + if (!regex.valid_) { + return false; + } +#ifdef NO_MORE_REGFREEE + return std::regex_match(str, str + std::strlen(str), match, regex.compiled_regex_); +#else + return regexMatch(std::string{str}, match, regex); +#endif +} + +bool regexMatch(const std::string_view& str, SVMatch& match, const Regex& regex) { if (!regex.valid_) { return false; } #ifdef NO_MORE_REGFREEE - return std::regex_search(string, regex.compiled_regex_); + return std::regex_match(std::cbegin(str), std::cend(str), match, regex.compiled_regex_); #else - std::vector<regmatch_t> match; - match.resize(getMaxGroupCountOfRegex(regex.regex_str_)); - return regexec(®ex.compiled_regex_, string.c_str(), match.size(), match.data(), 0) == 0; + return regexMatch(std::string{str}, match, regex); #endif } -bool regexSearch(const std::string &string, SMatch& match, const Regex& regex) { +bool regexMatch(const std::string& str, SMatch& match, const Regex& regex) { if (!regex.valid_) { return false; } #ifdef NO_MORE_REGFREEE - return std::regex_search(string, match, regex.compiled_regex_); + return std::regex_match(str, match, regex.compiled_regex_); #else - match.clear(); - std::vector<regmatch_t> regmatches; - regmatches.resize(getMaxGroupCountOfRegex(regex.regex_str_)); - bool result = regexec(®ex.compiled_regex_, string.c_str(), regmatches.size(), regmatches.data(), 0) == 0; - match.string_ = string; - for (const auto& regmatch : regmatches) { - match.matches_.push_back(SMatch::Regmatch{regmatch, match.string_}); + match.reset(str); + match.ready_ = true; + std::vector<regmatch_t> regmatches(regex.compiled_full_input_regex_.re_nsub + 1); + bool result = regexec(®ex.compiled_full_input_regex_, str.c_str(), regmatches.size(), regmatches.data(), 0) == 0; + if (result) { + match.suffix_ = SMatch::Regmatch{true, match.string_.begin() + regmatches[0].rm_eo, match.string_.end()}; + for (const auto& regmatch : regmatches) { + bool matched = regmatch.rm_so != -1; + if (matched) { + auto begin = match.string_.begin() + regmatch.rm_so; + auto end = match.string_.begin() + regmatch.rm_eo; + match.matches_.emplace_back(true, begin, end); + } else { + match.matches_.emplace_back(false, match.string_.end(), match.string_.end()); + } + } } return result; #endif } -bool regexMatch(const std::string &string, const Regex& regex) { +bool regexSearch(const char* str, const Regex& regex) { + CMatch match; + return regexSearch(str, match, regex); +} + +bool regexSearch(const std::string_view& str, const Regex& regex) { + SVMatch match; + return regexSearch(str, match, regex); +} + +bool regexSearch(const std::string& str, const Regex& regex) { + SMatch match; + return regexSearch(str, match, regex); +} + +bool regexSearch(const char* str, CMatch& match, const Regex& regex) { + if (!regex.valid_) { + return false; + } +#ifdef NO_MORE_REGFREEE + return std::regex_search(str, str + std::strlen(str), match, regex.compiled_regex_); +#else + return regexSearch(std::string{str}, match, regex); +#endif +} + +bool regexSearch(const std::string_view& str, SVMatch& match, const Regex& regex) { if (!regex.valid_) { return false; } #ifdef NO_MORE_REGFREEE - return std::regex_match(string, regex.compiled_regex_); + return std::regex_search(std::cbegin(str), std::cend(str), match, regex.compiled_regex_); #else - std::vector<regmatch_t> match; - match.resize(getMaxGroupCountOfRegex(regex.regex_str_)); - return regexec(®ex.compiled_full_input_regex_, string.c_str(), match.size(), match.data(), 0) == 0; + return regexSearch(std::string{str}, match, regex); #endif } -bool regexMatch(const std::string &string, SMatch& match, const Regex& regex) { +bool regexSearch(const std::string& str, SMatch& match, const Regex& regex) { if (!regex.valid_) { return false; } #ifdef NO_MORE_REGFREEE - return std::regex_match(string, match, regex.compiled_regex_); + return std::regex_search(str, match, regex.compiled_regex_); #else - match.clear(); - std::vector<regmatch_t> regmatches; - regmatches.resize(getMaxGroupCountOfRegex(regex.regex_str_)); - bool result = regexec(®ex.compiled_full_input_regex_, string.c_str(), regmatches.size(), regmatches.data(), 0) == 0; - match.string_ = string; - for (const auto& regmatch : regmatches) { - match.matches_.push_back(SMatch::Regmatch{regmatch, match.string_}); + match.reset(str); + match.ready_ = true; + std::vector<regmatch_t> regmatches(regex.compiled_regex_.re_nsub + 1); + bool result = regexec(®ex.compiled_regex_, str.c_str(), regmatches.size(), regmatches.data(), 0) == 0; + if (result) { + match.suffix_ = SMatch::Regmatch{true, match.string_.begin() + regmatches[0].rm_eo, match.string_.end()}; + for (const auto& regmatch : regmatches) { + bool matched = regmatch.rm_so != -1; + if (matched) { + auto begin = match.string_.begin() + regmatch.rm_so; + auto end = match.string_.begin() + regmatch.rm_eo; + match.matches_.emplace_back(true, begin, end); + } else { + match.matches_.emplace_back(false, match.string_.end(), match.string_.end()); + } + } } return result; #endif @@ -279,13 +372,39 @@ SMatch getLastRegexMatch(const std::string& string, const utils::Regex& regex) { current_str = search_result.suffix(); } - auto diff = string.size() - last_match.string_.size(); - last_match.string_ = string; + if (!last_match.ready()) { + return last_match; + } + + struct MatchInfo { + bool matched; + size_t begin; + size_t end; + }; + + // we must save the sub matches' info in a way that does + // not get invalidated by SMatch::reset, and can be transferred + // to the updated match + std::vector<MatchInfo> match_infos; + match_infos.reserve(last_match.size()); for (auto& match : last_match.matches_) { - if (match.match.rm_so >= 0) { - match.match.rm_so += diff; - match.match.rm_eo += diff; - } + match_infos.emplace_back(MatchInfo{ + .matched = match.matched, + .begin = gsl::narrow<size_t>(std::distance(last_match.string_.cbegin(), match.first)), + .end = gsl::narrow<size_t>(std::distance(last_match.string_.cbegin(), match.second)) + }); + } + // offset of the start of the last match into the original string + auto offset = string.size() - last_match.string_.size(); + last_match.reset(string); + last_match.ready_ = true; + for (auto& info : match_infos) { + size_t match_off = info.matched ? offset : 0; + last_match.matches_.emplace_back(SMatch::Regmatch{ + info.matched, + last_match.string_.cbegin() + info.begin + match_off, + last_match.string_.cbegin() + info.end + match_off + }); } return last_match; #endif diff --git a/libminifi/test/unit/RegexUtilsTests.cpp b/libminifi/test/unit/RegexUtilsTests.cpp index 40a50509b..3486a7c77 100644 --- a/libminifi/test/unit/RegexUtilsTests.cpp +++ b/libminifi/test/unit/RegexUtilsTests.cpp @@ -125,3 +125,55 @@ TEST_CASE("TestRegexUtils::getLastRegexMatch works correctly", "[getLastRegexMat CHECK(last_match.position(0) == 21); } } + +TEST_CASE("TestRegexUtils::regexMatch works with const char*", "[matchConstChar]") { + std::string pat = "Speed limit 130 all the way"; + std::string rgx1 = "Speed limit ([0-9]+) (.*)"; + Regex r1(rgx1); + minifi::utils::CMatch matches; + REQUIRE(minifi::utils::regexMatch(pat.c_str(), matches, r1)); + REQUIRE(matches.size() == 3); + REQUIRE(matches[0].str() == "Speed limit 130 all the way"); + REQUIRE(matches[1].str() == "130"); + REQUIRE(matches[2].str() == "all the way"); + REQUIRE(matches.suffix().str().empty()); +} + +TEST_CASE("TestRegexUtils::regexMatch works with std::string_view", "[matchStringView]") { + std::string pat = "Speed limit 130 all the way"; + std::string rgx1 = "Speed limit ([0-9]+) (.*)"; + Regex r1(rgx1); + minifi::utils::SVMatch matches; + REQUIRE(minifi::utils::regexMatch(std::string_view{pat}, matches, r1)); + REQUIRE(matches.size() == 3); + REQUIRE(matches[0].str() == "Speed limit 130 all the way"); + REQUIRE(matches[1].str() == "130"); + REQUIRE(matches[2].str() == "all the way"); + REQUIRE(matches.suffix().str().empty()); +} + +TEST_CASE("TestRegexUtils::regexSearch works with const char*", "[searchConstChar]") { + std::string pat = "Speed limit 130 all the way"; + std::string rgx1 = "Speed limit ([0-9]+) (.*)"; + Regex r1(rgx1); + minifi::utils::CMatch matches; + REQUIRE(minifi::utils::regexSearch(pat.c_str(), matches, r1)); + REQUIRE(matches.size() == 3); + REQUIRE(matches[0].str() == "Speed limit 130 all the way"); + REQUIRE(matches[1].str() == "130"); + REQUIRE(matches[2].str() == "all the way"); + REQUIRE(matches.suffix().str().empty()); +} + +TEST_CASE("TestRegexUtils::regexSearch works with std::string_view", "[searchStringView]") { + std::string pat = "Speed limit 130 all the way"; + std::string rgx1 = "Speed limit ([0-9]+) (.*)"; + Regex r1(rgx1); + minifi::utils::SVMatch matches; + REQUIRE(minifi::utils::regexSearch(std::string_view{pat}, matches, r1)); + REQUIRE(matches.size() == 3); + REQUIRE(matches[0].str() == "Speed limit 130 all the way"); + REQUIRE(matches[1].str() == "130"); + REQUIRE(matches[2].str() == "all the way"); + REQUIRE(matches.suffix().str().empty()); +}
