You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2019/02/08 15:35:28 UTC
[trafficserver] branch master updated: DFA: Update DFA to use
string_view.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new ef780ea DFA: Update DFA to use string_view.
ef780ea is described below
commit ef780ea0b5b212d9a5667f1160496445f2450a78
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Tue Jan 15 12:48:27 2019 -0600
DFA: Update DFA to use string_view.
---
include/tscore/Regex.h | 51 +++++++++++-----
iocore/net/P_SSLUtils.h | 2 +-
lib/records/RecCore.cc | 2 +-
proxy/hdrs/HdrToken.cc | 2 +-
proxy/hdrs/MIME.cc | 9 +--
src/traffic_cache_tool/CacheDefs.h | 19 ++----
src/tscore/Regex.cc | 120 ++++++++++++-------------------------
7 files changed, 89 insertions(+), 116 deletions(-)
diff --git a/include/tscore/Regex.h b/include/tscore/Regex.h
index f80121e..3c95b27 100644
--- a/include/tscore/Regex.h
+++ b/include/tscore/Regex.h
@@ -24,6 +24,9 @@
#pragma once
#include <string_view>
+#include <string>
+#include <vector>
+#include <memory>
#include "tscore/ink_config.h"
@@ -49,7 +52,9 @@ public:
/// Default number of capture groups.
static constexpr size_t DEFAULT_GROUP_COUNT = 10;
- Regex() = default;
+ Regex() = default;
+ Regex(Regex const &) = delete; // No copying.
+ Regex(Regex &&that) noexcept;
~Regex();
/** Compile the @a pattern into a regular expression.
@@ -60,7 +65,7 @@ public:
*
* @a flags should be the bitwise @c or of @c REFlags values.
*/
- bool compile(const char *pattern, const unsigned flags = 0);
+ bool compile(const char *pattern, unsigned flags = 0);
/** Execute the regular expression.
*
@@ -93,27 +98,45 @@ private:
pcre_extra *regex_extra = nullptr;
};
-typedef struct __pat {
- int _idx;
- Regex *_re;
- char *_p;
- __pat *_next;
-} dfa_pattern;
-
+/** Deterministic Finite state Automata container.
+ *
+ * This contains a set of patterns (which may be of size 1) and matches if any of the patterns
+ * match.
+ */
class DFA
{
public:
DFA() = default;
~DFA();
- int compile(const char *pattern, unsigned flags = 0);
+ /// @return The number of patterns successfully compiled.
+ int compile(std::string_view const &pattern, unsigned flags = 0);
+ /// @return The number of patterns successfully compiled.
+ int compile(std::string_view *patterns, int npatterns, unsigned flags = 0);
+ /// @return The number of patterns successfully compiled.
int compile(const char **patterns, int npatterns, unsigned flags = 0);
- int match(const char *str) const;
- int match(const char *str, int length) const;
+ /** Match @a str against the internal patterns.
+ *
+ * @param str String to match.
+ * @return Index of the matched pattern, -1 if no match.
+ */
+ int match(std::string_view const &str) const;
private:
- dfa_pattern *build(const char *pattern, unsigned flags = 0);
+ struct Pattern {
+ Pattern(Regex &&rxp, std::string &&s) : _re(std::move(rxp)), _p(std::move(s)) {}
+ Regex _re; ///< The compile pattern.
+ std::string _p; ///< The original pattern.
+ };
+
+ /** Compile @a pattern and add it to the pattern set.
+ *
+ * @param pattern Regular expression to compile.
+ * @param flags Regular expression compilation flags.
+ * @return @c true if @a pattern was successfully compiled, @c false if not.
+ */
+ bool build(std::string_view const &pattern, unsigned flags = 0);
- dfa_pattern *_my_patterns = nullptr;
+ std::vector<Pattern> _patterns;
};
diff --git a/iocore/net/P_SSLUtils.h b/iocore/net/P_SSLUtils.h
index e3ec9f6..6990db6 100644
--- a/iocore/net/P_SSLUtils.h
+++ b/iocore/net/P_SSLUtils.h
@@ -227,7 +227,7 @@ namespace detail
struct ats_wildcard_matcher {
ats_wildcard_matcher()
{
- if (regex.compile("^\\*\\.[^\\*.]+") != 0) {
+ if (!regex.compile("^\\*\\.[^\\*.]+")) {
Fatal("failed to compile TLS wildcard matching regex");
}
}
diff --git a/lib/records/RecCore.cc b/lib/records/RecCore.cc
index 388a69b..68dd6fa 100644
--- a/lib/records/RecCore.cc
+++ b/lib/records/RecCore.cc
@@ -497,7 +497,7 @@ RecLookupMatchingRecords(unsigned rec_type, const char *match, void (*callback)(
int num_records;
DFA regex;
- if (regex.compile(match, RE_CASE_INSENSITIVE | RE_UNANCHORED) != 0) {
+ if (!regex.compile(match, RE_CASE_INSENSITIVE | RE_UNANCHORED)) {
return REC_ERR_FAIL;
}
diff --git a/proxy/hdrs/HdrToken.cc b/proxy/hdrs/HdrToken.cc
index 55fe520..7775992 100644
--- a/proxy/hdrs/HdrToken.cc
+++ b/proxy/hdrs/HdrToken.cc
@@ -522,7 +522,7 @@ hdrtoken_tokenize_dfa(const char *string, int string_len, const char **wks_strin
{
int wks_idx;
- wks_idx = hdrtoken_strs_dfa->match(string, string_len);
+ wks_idx = hdrtoken_strs_dfa->match({string, size_t(string_len)});
if (wks_idx < 0) {
wks_idx = -1;
diff --git a/proxy/hdrs/MIME.cc b/proxy/hdrs/MIME.cc
index 33ab602..81c4622 100644
--- a/proxy/hdrs/MIME.cc
+++ b/proxy/hdrs/MIME.cc
@@ -3282,6 +3282,7 @@ int
mime_parse_rfc822_date_fastcase(const char *buf, int length, struct tm *tp)
{
unsigned int three_char_wday, three_char_mon;
+ std::string_view view{buf, size_t(length)};
ink_assert(length >= 29);
ink_assert(!is_ws(buf[0]));
@@ -3312,7 +3313,7 @@ mime_parse_rfc822_date_fastcase(const char *buf, int length, struct tm *tp)
}
}
if (tp->tm_wday < 0) {
- tp->tm_wday = day_names_dfa->match(buf, length);
+ tp->tm_wday = day_names_dfa->match(view);
if (tp->tm_wday < 0) {
return 0;
}
@@ -3365,7 +3366,7 @@ mime_parse_rfc822_date_fastcase(const char *buf, int length, struct tm *tp)
}
}
if (tp->tm_mon < 0) {
- tp->tm_mon = month_names_dfa->match(buf, length);
+ tp->tm_mon = month_names_dfa->match(view);
if (tp->tm_mon < 0) {
return 0;
}
@@ -3510,7 +3511,7 @@ mime_parse_day(const char *&buf, const char *end, int *day)
e += 1;
}
- *day = day_names_dfa->match(buf, e - buf);
+ *day = day_names_dfa->match({buf, size_t(e - buf)});
if (*day < 0) {
return 0;
} else {
@@ -3533,7 +3534,7 @@ mime_parse_month(const char *&buf, const char *end, int *month)
e += 1;
}
- *month = month_names_dfa->match(buf, e - buf);
+ *month = month_names_dfa->match({buf, size_t(e - buf)});
if (*month < 0) {
return 0;
} else {
diff --git a/src/traffic_cache_tool/CacheDefs.h b/src/traffic_cache_tool/CacheDefs.h
index 4a98082..db5fd14 100644
--- a/src/traffic_cache_tool/CacheDefs.h
+++ b/src/traffic_cache_tool/CacheDefs.h
@@ -300,11 +300,11 @@ struct url_matcher {
for (i = 0; i < count; i++) {
std::cout << "regex " << patterns[i] << std::endl;
}
- if (regex.compile(patterns, count) != 0) {
+ if (regex.compile(patterns, count) != count) {
std::cout << "Check your regular expression" << std::endl;
}
- if (port.compile(R"([0-9]+$)") != 0) {
+ if (!port.compile(R"([0-9]+$)")) {
std::cout << "Check your regular expression" << std::endl;
return;
}
@@ -313,11 +313,11 @@ struct url_matcher {
url_matcher()
{
- if (regex.compile(R"(^(https?\:\/\/)") != 0) {
+ if (!regex.compile(R"(^(https?\:\/\/)")) {
std::cout << "Check your regular expression" << std::endl;
return;
}
- if (port.compile(R"([0-9]+$)") != 0) {
+ if (!port.compile(R"([0-9]+$)")) {
std::cout << "Check your regular expression" << std::endl;
return;
}
@@ -328,19 +328,12 @@ struct url_matcher {
uint8_t
match(const char *hostname) const
{
- if (regex.match(hostname) != -1) {
- return 1;
- }
-
- return 0;
+ return regex.match(hostname) ? 1 : 0;
}
uint8_t
portmatch(const char *hostname, int length) const
{
- if (port.match(hostname, length) != -1) {
- return 1;
- }
- return 0;
+ return port.match({hostname, size_t(length)}) ? 1 : 0;
}
private:
diff --git a/src/tscore/Regex.cc b/src/tscore/Regex.cc
index d067072..d0a7a8b 100644
--- a/src/tscore/Regex.cc
+++ b/src/tscore/Regex.cc
@@ -50,6 +50,12 @@ get_jit_stack(void *data ATS_UNUSED)
}
#endif
+Regex::Regex(Regex &&that) noexcept : regex(that.regex), regex_extra(that.regex_extra)
+{
+ that.regex = nullptr;
+ that.regex_extra = nullptr;
+}
+
bool
Regex::compile(const char *pattern, const unsigned flags)
{
@@ -114,7 +120,7 @@ Regex::exec(std::string_view const &str, int *ovector, int ovecsize)
{
int rv;
- rv = pcre_exec(regex, regex_extra, str.data(), str.size(), 0, 0, ovector, ovecsize);
+ rv = pcre_exec(regex, regex_extra, str.data(), int(str.size()), 0, 0, ovector, ovecsize);
return rv > 0;
}
@@ -132,113 +138,63 @@ Regex::~Regex()
}
}
-DFA::~DFA()
-{
- dfa_pattern *p = _my_patterns;
- dfa_pattern *t;
+DFA::~DFA() {}
- while (p) {
- if (p->_re) {
- delete p->_re;
- }
- if (p->_p) {
- ats_free(p->_p);
- }
- t = p->_next;
- ats_free(p);
- p = t;
- }
-}
-
-dfa_pattern *
-DFA::build(const char *pattern, unsigned flags)
+bool
+DFA::build(std::string_view const &pattern, unsigned flags)
{
- dfa_pattern *ret;
- int rv;
+ Regex rxp;
+ std::string string{pattern};
if (!(flags & RE_UNANCHORED)) {
flags |= RE_ANCHORED;
}
- ret = (dfa_pattern *)ats_malloc(sizeof(dfa_pattern));
- ret->_p = nullptr;
-
- ret->_re = new Regex();
- rv = ret->_re->compile(pattern, flags);
- if (rv == -1) {
- delete ret->_re;
- ats_free(ret);
- return nullptr;
+ if (!rxp.compile(string.c_str(), flags)) {
+ return false;
}
-
- ret->_idx = 0;
- ret->_p = ats_strndup(pattern, strlen(pattern));
- ret->_next = nullptr;
- return ret;
+ _patterns.emplace_back(std::move(rxp), std::move(string));
+ return true;
}
int
-DFA::compile(const char *pattern, unsigned flags)
+DFA::compile(std::string_view const &pattern, unsigned flags)
{
- ink_assert(_my_patterns == nullptr);
- _my_patterns = build(pattern, flags);
- if (_my_patterns) {
- return 0;
- } else {
- return -1;
- }
+ ink_assert(_patterns.empty());
+ this->build(pattern, flags);
+ return _patterns.size();
}
int
-DFA::compile(const char **patterns, int npatterns, unsigned flags)
+DFA::compile(std::string_view *patterns, int npatterns, unsigned flags)
{
- const char *pattern;
- dfa_pattern *ret = nullptr;
- dfa_pattern *end = nullptr;
- int i;
-
- for (i = 0; i < npatterns; i++) {
- pattern = patterns[i];
- ret = build(pattern, flags);
- if (!ret) {
- continue;
- }
-
- if (!_my_patterns) {
- _my_patterns = ret;
- _my_patterns->_next = nullptr;
- _my_patterns->_idx = i;
- } else {
- end = _my_patterns;
- while (end->_next) {
- end = end->_next;
- }
- end->_next = ret; // add to end
- ret->_idx = i;
- }
+ _patterns.reserve(npatterns); // try to pre-allocate.
+ for (int i = 0; i < npatterns; ++i) {
+ this->build(patterns[i], flags);
}
-
- return 0;
+ return _patterns.size();
}
int
-DFA::match(const char *str) const
+DFA::compile(const char **patterns, int npatterns, unsigned flags)
{
- return match(str, strlen(str));
+ _patterns.reserve(npatterns); // try to pre-allocate.
+ for (int i = 0; i < npatterns; ++i) {
+ this->build(patterns[i], flags);
+ }
+ return _patterns.size();
}
int
-DFA::match(const char *str, int length) const
+DFA::match(std::string_view const &str) const
{
- int rc;
- dfa_pattern *p = _my_patterns;
-
- while (p) {
- rc = p->_re->exec({str, size_t(length)});
- if (rc > 0) {
- return p->_idx;
+ // This is ugly, but the external interface needs to be @c const even though it's not really.
+ // This handles making the iterator non-const.
+ auto &pv{const_cast<decltype(_patterns) &>(_patterns)};
+ for (auto spot = pv.begin(), limit = pv.end(); spot != limit; ++spot) {
+ if (spot->_re.exec(str)) {
+ return spot - _patterns.begin();
}
- p = p->_next;
}
return -1;