Script 'mail_helper' called by obssrc
Hello community,
here is the log from the commit of package re2 for openSUSE:Factory checked in
at 2021-08-12 09:00:56
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/re2 (Old)
and /work/SRC/openSUSE:Factory/.re2.new.1899 (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "re2"
Thu Aug 12 09:00:56 2021 rev:39 rq:910541 version:MACRO
Changes:
--------
--- /work/SRC/openSUSE:Factory/re2/re2.changes 2021-06-14 23:10:42.212709089
+0200
+++ /work/SRC/openSUSE:Factory/.re2.new.1899/re2.changes 2021-08-12
09:01:40.474150212 +0200
@@ -1,0 +2,6 @@
+Fri Aug 6 20:21:06 UTC 2021 - Andreas Stieger <andreas.stie...@gmx.de>
+
+- update to 2021-08-01:
+ * case-insensitive prefix acceleration
+
+-------------------------------------------------------------------
Old:
----
re2-2021-06-01.tar.gz
New:
----
re2-2021-08-01.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ re2.spec ++++++
--- /var/tmp/diff_new_pack.8QJJ37/_old 2021-08-12 09:01:40.946149460 +0200
+++ /var/tmp/diff_new_pack.8QJJ37/_new 2021-08-12 09:01:40.950149453 +0200
@@ -16,7 +16,7 @@
#
-%global longver 2021-06-01
+%global longver 2021-08-01
%global shortver %(echo %{longver}|sed 's|-||g')
%define libname libre2-9
Name: re2
++++++ re2-2021-06-01.tar.gz -> re2-2021-08-01.tar.gz ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/.github/workflows/ci-bazel.yml
new/re2-2021-08-01/.github/workflows/ci-bazel.yml
--- old/re2-2021-06-01/.github/workflows/ci-bazel.yml 2021-05-21
13:25:31.000000000 +0200
+++ new/re2-2021-08-01/.github/workflows/ci-bazel.yml 2021-07-24
13:39:54.000000000 +0200
@@ -1,7 +1,7 @@
name: CI (Bazel)
on:
push:
- branches: [master]
+ branches: [main]
jobs:
build:
runs-on: ${{ matrix.os }}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/.github/workflows/ci-cmake.yml
new/re2-2021-08-01/.github/workflows/ci-cmake.yml
--- old/re2-2021-06-01/.github/workflows/ci-cmake.yml 2021-05-21
13:25:31.000000000 +0200
+++ new/re2-2021-08-01/.github/workflows/ci-cmake.yml 2021-07-24
13:39:54.000000000 +0200
@@ -1,7 +1,7 @@
name: CI (CMake)
on:
push:
- branches: [master]
+ branches: [main]
jobs:
build:
runs-on: ${{ matrix.os }}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/.github/workflows/ci.yml
new/re2-2021-08-01/.github/workflows/ci.yml
--- old/re2-2021-06-01/.github/workflows/ci.yml 2021-05-21 13:25:31.000000000
+0200
+++ new/re2-2021-08-01/.github/workflows/ci.yml 2021-07-24 13:39:54.000000000
+0200
@@ -1,7 +1,7 @@
name: CI
on:
push:
- branches: [master]
+ branches: [main]
jobs:
build:
runs-on: ${{ matrix.os }}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/SECURITY.md
new/re2-2021-08-01/SECURITY.md
--- old/re2-2021-06-01/SECURITY.md 1970-01-01 01:00:00.000000000 +0100
+++ new/re2-2021-08-01/SECURITY.md 2021-07-24 13:39:54.000000000 +0200
@@ -0,0 +1,4 @@
+To report a security issue, please use https://g.co/vulnz. We use
+https://g.co/vulnz for our intake, and do coordination and disclosure here on
+GitHub (including using GitHub Security Advisory). The Google Security Team
will
+respond within 5 working days of your report on https://g.co/vulnz.
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/WORKSPACE new/re2-2021-08-01/WORKSPACE
--- old/re2-2021-06-01/WORKSPACE 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/WORKSPACE 2021-07-24 13:39:54.000000000 +0200
@@ -10,6 +10,6 @@
http_archive(
name = "rules_cc",
- strip_prefix = "rules_cc-master",
- urls = ["https://github.com/bazelbuild/rules_cc/archive/master.zip";],
+ strip_prefix = "rules_cc-main",
+ urls = ["https://github.com/bazelbuild/rules_cc/archive/main.zip";],
)
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/compile.cc
new/re2-2021-08-01/re2/compile.cc
--- old/re2-2021-06-01/re2/compile.cc 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/compile.cc 2021-07-24 13:39:54.000000000 +0200
@@ -1176,12 +1176,8 @@
if (!prog_->reversed()) {
std::string prefix;
bool prefix_foldcase;
- if (re->RequiredPrefixForAccel(&prefix, &prefix_foldcase) &&
- !prefix_foldcase) {
- prog_->prefix_size_ = prefix.size();
- prog_->prefix_front_ = prefix.front();
- prog_->prefix_back_ = prefix.back();
- }
+ if (re->RequiredPrefixForAccel(&prefix, &prefix_foldcase))
+ prog_->ConfigurePrefixAccel(prefix, prefix_foldcase);
}
// Record remaining memory for DFA.
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/dfa.cc
new/re2-2021-08-01/re2/dfa.cc
--- old/re2-2021-06-01/re2/dfa.cc 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/dfa.cc 2021-07-24 13:39:54.000000000 +0200
@@ -56,6 +56,10 @@
// Controls whether the DFA should bail out early if the NFA would be faster.
static bool dfa_should_bail_when_slow = true;
+void Prog::TESTING_ONLY_set_dfa_should_bail_when_slow(bool b) {
+ dfa_should_bail_when_slow = b;
+}
+
// Changing this to true compiles in prints that trace execution of the DFA.
// Generates a lot of output -- only useful for debugging.
static const bool ExtraDebug = false;
@@ -1966,10 +1970,6 @@
return GetDFA(kind)->BuildAllStates(cb);
}
-void Prog::TEST_dfa_should_bail_when_slow(bool b) {
- dfa_should_bail_when_slow = b;
-}
-
// Computes min and max for matching string.
// Won't return strings bigger than maxlen.
bool DFA::PossibleMatchRange(std::string* min, std::string* max, int maxlen) {
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/fuzzing/re2_fuzzer.cc
new/re2-2021-08-01/re2/fuzzing/re2_fuzzer.cc
--- old/re2-2021-06-01/re2/fuzzing/re2_fuzzer.cc 2021-05-21
13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/fuzzing/re2_fuzzer.cc 2021-07-24
13:39:54.000000000 +0200
@@ -12,6 +12,7 @@
#include "re2/prefilter.h"
#include "re2/re2.h"
+#include "re2/regexp.h"
using re2::StringPiece;
@@ -50,6 +51,10 @@
if (backslash_p > 1)
return;
+ // The default is 1000. Even 100 turned out to be too generous
+ // for fuzzing, empirically speaking, so let's try 10 instead.
+ re2::Regexp::FUZZING_ONLY_set_maximum_repeat_count(10);
+
RE2 re(pattern, options);
if (!re.ok())
return;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/parse.cc
new/re2-2021-08-01/re2/parse.cc
--- old/re2-2021-06-01/re2/parse.cc 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/parse.cc 2021-07-24 13:39:54.000000000 +0200
@@ -44,12 +44,12 @@
namespace re2 {
-// Reduce the maximum repeat count by an order of magnitude when fuzzing.
-#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
-static const int kMaxRepeat = 100;
-#else
-static const int kMaxRepeat = 1000;
-#endif
+// Controls the maximum repeat count permitted by the parser.
+static int maximum_repeat_count = 1000;
+
+void Regexp::FUZZING_ONLY_set_maximum_repeat_count(int i) {
+ maximum_repeat_count = i;
+}
// Regular expression parse state.
// The list of parsed regexps so far is maintained as a vector of
@@ -568,7 +568,9 @@
bool Regexp::ParseState::PushRepetition(int min, int max,
const StringPiece& s,
bool nongreedy) {
- if ((max != -1 && max < min) || min > kMaxRepeat || max > kMaxRepeat) {
+ if ((max != -1 && max < min) ||
+ min > maximum_repeat_count ||
+ max > maximum_repeat_count) {
status_->set_code(kRegexpRepeatSize);
status_->set_error_arg(s);
return false;
@@ -591,7 +593,7 @@
stacktop_ = re;
if (min >= 2 || max >= 2) {
RepetitionWalker w;
- if (w.Walk(stacktop_, kMaxRepeat) == 0) {
+ if (w.Walk(stacktop_, maximum_repeat_count) == 0) {
status_->set_code(kRegexpRepeatSize);
status_->set_error_arg(s);
return false;
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/prog.cc
new/re2-2021-08-01/re2/prog.cc
--- old/re2-2021-06-01/re2/prog.cc 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/prog.cc 2021-07-24 13:39:54.000000000 +0200
@@ -115,9 +115,8 @@
start_unanchored_(0),
size_(0),
bytemap_range_(0),
+ prefix_foldcase_(false),
prefix_size_(0),
- prefix_front_(-1),
- prefix_back_(-1),
list_count_(0),
dfa_mem_(0),
dfa_first_(NULL),
@@ -127,6 +126,8 @@
Prog::~Prog() {
DeleteDFA(dfa_longest_);
DeleteDFA(dfa_first_);
+ if (prefix_foldcase_)
+ delete[] prefix_dfa_;
}
typedef SparseSet Workq;
@@ -916,6 +917,183 @@
}
}
+// The final state will always be this, which frees up a register for the hot
+// loop and thus avoids the spilling that can occur when building with Clang.
+static const size_t kShiftDFAFinal = 9;
+
+// This function takes the prefix as std::string (i.e. not const std::string&
+// as normal) because it's going to clobber it, so a temporary is convenient.
+static uint64_t* BuildShiftDFA(std::string prefix) {
+ // This constant is for convenience now and also for correctness later when
+ // we clobber the prefix, but still need to know how long it was initially.
+ const size_t size = prefix.size();
+
+ // Construct the NFA.
+ // The table is indexed by input byte; each element is a bitfield of states
+ // reachable by the input byte. Given a bitfield of the current states, the
+ // bitfield of states reachable from those is - for this specific purpose -
+ // always ((ncurr << 1) | 1). Intersecting the reachability bitfields gives
+ // the bitfield of the next states reached by stepping over the input byte.
+ // Credits for this technique: the Hyperscan paper by Geoff Langdale et al.
+ uint16_t nfa[256]{};
+ for (size_t i = 0; i < size; ++i) {
+ uint8_t b = prefix[i];
+ nfa[b] |= 1 << (i+1);
+ }
+ // This is the `\C*?` for unanchored search.
+ for (int b = 0; b < 256; ++b)
+ nfa[b] |= 1;
+
+ // This maps from DFA state to NFA states; the reverse mapping is used when
+ // recording transitions and gets implemented with plain old linear search.
+ // The "Shift DFA" technique limits this to ten states when using uint64_t;
+ // to allow for the initial state, we use at most nine bytes of the prefix.
+ // That same limit is also why uint16_t is sufficient for the NFA bitfield.
+ uint16_t states[kShiftDFAFinal+1]{};
+ states[0] = 1;
+ for (size_t dcurr = 0; dcurr < size; ++dcurr) {
+ uint8_t b = prefix[dcurr];
+ uint16_t ncurr = states[dcurr];
+ uint16_t nnext = nfa[b] & ((ncurr << 1) | 1);
+ size_t dnext = dcurr+1;
+ if (dnext == size)
+ dnext = kShiftDFAFinal;
+ states[dnext] = nnext;
+ }
+
+ // Sort and unique the bytes of the prefix to avoid repeating work while we
+ // record transitions. This clobbers the prefix, but it's no longer needed.
+ std::sort(prefix.begin(), prefix.end());
+ prefix.erase(std::unique(prefix.begin(), prefix.end()), prefix.end());
+
+ // Construct the DFA.
+ // The table is indexed by input byte; each element is effectively a packed
+ // array of uint6_t; each array value will be multiplied by six in order to
+ // avoid having to do so later in the hot loop as well as masking/shifting.
+ // Credits for this technique: "Shift-based DFAs" on GitHub by Per Vognsen.
+ uint64_t* dfa = new uint64_t[256]{};
+ // Record a transition from each state for each of the bytes of the prefix.
+ // Note that all other input bytes go back to the initial state by default.
+ for (size_t dcurr = 0; dcurr < size; ++dcurr) {
+ for (uint8_t b : prefix) {
+ uint16_t ncurr = states[dcurr];
+ uint16_t nnext = nfa[b] & ((ncurr << 1) | 1);
+ size_t dnext = 0;
+ while (states[dnext] != nnext)
+ ++dnext;
+ dfa[b] |= static_cast<uint64_t>(dnext * 6) << (dcurr * 6);
+ // Convert ASCII letters to uppercase and record the extra transitions.
+ // Note that ASCII letters are guaranteed to be lowercase at this point
+ // because that's how the parser normalises them. #FunFact: 'k' and 's'
+ // match U+212A and U+017F, respectively, so they won't occur here when
+ // using UTF-8 encoding because the parser will emit character classes.
+ if ('a' <= b && b <= 'z') {
+ b -= 'a' - 'A';
+ dfa[b] |= static_cast<uint64_t>(dnext * 6) << (dcurr * 6);
+ }
+ }
+ }
+ // This lets the final state "saturate", which will matter for performance:
+ // in the hot loop, we check for a match only at the end of each iteration,
+ // so we must keep signalling the match until we get around to checking it.
+ for (int b = 0; b < 256; ++b)
+ dfa[b] |= static_cast<uint64_t>(kShiftDFAFinal * 6) << (kShiftDFAFinal *
6);
+
+ return dfa;
+}
+
+void Prog::ConfigurePrefixAccel(const std::string& prefix,
+ bool prefix_foldcase) {
+ prefix_foldcase_ = prefix_foldcase;
+ prefix_size_ = prefix.size();
+ if (prefix_foldcase_) {
+ // Use PrefixAccel_ShiftDFA().
+ // ... and no more than nine bytes of the prefix. (See above for details.)
+ prefix_size_ = std::min(prefix_size_, kShiftDFAFinal);
+ prefix_dfa_ = BuildShiftDFA(prefix.substr(0, prefix_size_));
+ } else if (prefix_size_ != 1) {
+ // Use PrefixAccel_FrontAndBack().
+ prefix_front_ = prefix.front();
+ prefix_back_ = prefix.back();
+ } else {
+ // Use memchr(3).
+ prefix_front_ = prefix.front();
+ }
+}
+
+const void* Prog::PrefixAccel_ShiftDFA(const void* data, size_t size) {
+ if (size < prefix_size_)
+ return NULL;
+
+ uint64_t curr = 0;
+
+ // At the time of writing, rough benchmarks on a Broadwell machine showed
+ // that this unroll factor (i.e. eight) achieves a speedup factor of two.
+ if (size >= 8) {
+ const uint8_t* p = reinterpret_cast<const uint8_t*>(data);
+ const uint8_t* endp = p + (size&~7);
+ do {
+ uint8_t b0 = p[0];
+ uint8_t b1 = p[1];
+ uint8_t b2 = p[2];
+ uint8_t b3 = p[3];
+ uint8_t b4 = p[4];
+ uint8_t b5 = p[5];
+ uint8_t b6 = p[6];
+ uint8_t b7 = p[7];
+
+ uint64_t next0 = prefix_dfa_[b0];
+ uint64_t next1 = prefix_dfa_[b1];
+ uint64_t next2 = prefix_dfa_[b2];
+ uint64_t next3 = prefix_dfa_[b3];
+ uint64_t next4 = prefix_dfa_[b4];
+ uint64_t next5 = prefix_dfa_[b5];
+ uint64_t next6 = prefix_dfa_[b6];
+ uint64_t next7 = prefix_dfa_[b7];
+
+ uint64_t curr0 = next0 >> (curr & 63);
+ uint64_t curr1 = next1 >> (curr0 & 63);
+ uint64_t curr2 = next2 >> (curr1 & 63);
+ uint64_t curr3 = next3 >> (curr2 & 63);
+ uint64_t curr4 = next4 >> (curr3 & 63);
+ uint64_t curr5 = next5 >> (curr4 & 63);
+ uint64_t curr6 = next6 >> (curr5 & 63);
+ uint64_t curr7 = next7 >> (curr6 & 63);
+
+ if ((curr7 & 63) == kShiftDFAFinal * 6) {
+ // At the time of writing, using the same masking subexpressions from
+ // the preceding lines caused Clang to clutter the hot loop computing
+ // them - even though they aren't actually needed for shifting! Hence
+ // these rewritten conditions, which achieve a speedup factor of two.
+ if (((curr7-curr0) & 63) == 0) return p+1-prefix_size_;
+ if (((curr7-curr1) & 63) == 0) return p+2-prefix_size_;
+ if (((curr7-curr2) & 63) == 0) return p+3-prefix_size_;
+ if (((curr7-curr3) & 63) == 0) return p+4-prefix_size_;
+ if (((curr7-curr4) & 63) == 0) return p+5-prefix_size_;
+ if (((curr7-curr5) & 63) == 0) return p+6-prefix_size_;
+ if (((curr7-curr6) & 63) == 0) return p+7-prefix_size_;
+ if (((curr7-curr7) & 63) == 0) return p+8-prefix_size_;
+ }
+
+ curr = curr7;
+ p += 8;
+ } while (p != endp);
+ data = p;
+ size = size&7;
+ }
+
+ const uint8_t* p = reinterpret_cast<const uint8_t*>(data);
+ const uint8_t* endp = p + size;
+ while (p != endp) {
+ uint8_t b = *p++;
+ uint64_t next = prefix_dfa_[b];
+ curr = next >> (curr & 63);
+ if ((curr & 63) == kShiftDFAFinal * 6)
+ return p-prefix_size_;
+ }
+ return NULL;
+}
+
#if defined(__AVX2__)
// Finds the least significant non-zero bit in n.
static int FindLSBSet(uint32_t n) {
@@ -958,7 +1136,7 @@
const __m256i* endfp = fp + size/sizeof(__m256i);
const __m256i f_set1 = _mm256_set1_epi8(prefix_front_);
const __m256i b_set1 = _mm256_set1_epi8(prefix_back_);
- while (fp != endfp) {
+ do {
const __m256i f_loadu = _mm256_loadu_si256(fp++);
const __m256i b_loadu = _mm256_loadu_si256(bp++);
const __m256i f_cmpeq = _mm256_cmpeq_epi8(f_set1, f_loadu);
@@ -970,7 +1148,7 @@
const int fb_ctz = FindLSBSet(fb_movemask);
return reinterpret_cast<const char*>(fp-1) + fb_ctz;
}
- }
+ } while (fp != endfp);
data = fp;
size = size%sizeof(__m256i);
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/prog.h
new/re2-2021-08-01/re2/prog.h
--- old/re2-2021-06-01/re2/prog.h 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/prog.h 2021-07-24 13:39:54.000000000 +0200
@@ -220,11 +220,23 @@
// Accelerates to the first likely occurrence of the prefix.
// Returns a pointer to the first byte or NULL if not found.
const void* PrefixAccel(const void* data, size_t size) {
- DCHECK_GE(prefix_size_, 1);
- return prefix_size_ == 1 ? memchr(data, prefix_front_, size)
- : PrefixAccel_FrontAndBack(data, size);
+ DCHECK(can_prefix_accel());
+ if (prefix_foldcase_) {
+ return PrefixAccel_ShiftDFA(data, size);
+ } else if (prefix_size_ != 1) {
+ return PrefixAccel_FrontAndBack(data, size);
+ } else {
+ return memchr(data, prefix_front_, size);
+ }
}
+ // Configures prefix accel using the analysis performed during compilation.
+ void ConfigurePrefixAccel(const std::string& prefix, bool prefix_foldcase);
+
+ // An implementation of prefix accel that uses prefix_dfa_ to perform
+ // case-insensitive search.
+ const void* PrefixAccel_ShiftDFA(const void* data, size_t size);
+
// An implementation of prefix accel that looks for prefix_front_ and
// prefix_back_ to return fewer false positives than memchr(3) alone.
const void* PrefixAccel_FrontAndBack(const void* data, size_t size);
@@ -298,10 +310,6 @@
// FOR TESTING OR EXPERIMENTAL PURPOSES ONLY.
int BuildEntireDFA(MatchKind kind, const DFAStateCallback& cb);
- // Controls whether the DFA should bail out early if the NFA would be faster.
- // FOR TESTING ONLY.
- static void TEST_dfa_should_bail_when_slow(bool b);
-
// Compute bytemap.
void ComputeByteMap();
@@ -390,6 +398,10 @@
// Computes hints for ByteRange instructions in [begin, end).
void ComputeHints(std::vector<Inst>* flat, int begin, int end);
+ // Controls whether the DFA should bail out early if the NFA would be faster.
+ // FOR TESTING ONLY.
+ static void TESTING_ONLY_set_dfa_should_bail_when_slow(bool b);
+
private:
friend class Compiler;
@@ -406,9 +418,16 @@
int start_unanchored_; // unanchored entry point for program
int size_; // number of instructions
int bytemap_range_; // bytemap_[x] < bytemap_range_
+
+ bool prefix_foldcase_; // whether prefix is case-insensitive
size_t prefix_size_; // size of prefix (0 if no prefix)
- int prefix_front_; // first byte of prefix (-1 if no prefix)
- int prefix_back_; // last byte of prefix (-1 if no prefix)
+ union {
+ uint64_t* prefix_dfa_; // "Shift DFA" for prefix
+ struct {
+ int prefix_front_; // first byte of prefix
+ int prefix_back_; // last byte of prefix
+ };
+ };
int list_count_; // count of lists (see above)
int inst_count_[kNumInst]; // count of instructions by opcode
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/regexp.h
new/re2-2021-08-01/re2/regexp.h
--- old/re2-2021-06-01/re2/regexp.h 2021-05-21 13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/regexp.h 2021-07-24 13:39:54.000000000 +0200
@@ -449,6 +449,10 @@
// regardless of the return value.
bool RequiredPrefixForAccel(std::string* prefix, bool* foldcase);
+ // Controls the maximum repeat count permitted by the parser.
+ // FOR FUZZING ONLY.
+ static void FUZZING_ONLY_set_maximum_repeat_count(int i);
+
private:
// Constructor allocates vectors as appropriate for operator.
explicit Regexp(RegexpOp op, ParseFlags parse_flags);
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/testing/dfa_test.cc
new/re2-2021-08-01/re2/testing/dfa_test.cc
--- old/re2-2021-06-01/re2/testing/dfa_test.cc 2021-05-21 13:25:31.000000000
+0200
+++ new/re2-2021-08-01/re2/testing/dfa_test.cc 2021-07-24 13:39:54.000000000
+0200
@@ -143,7 +143,7 @@
// NFA implementation instead. (The DFA loses its speed advantage
// if it can't get a good cache hit rate.)
// Tell the DFA to trudge along instead.
- Prog::TEST_dfa_should_bail_when_slow(false);
+ Prog::TESTING_ONLY_set_dfa_should_bail_when_slow(false);
state_cache_resets = 0;
search_failures = 0;
@@ -194,7 +194,7 @@
re->Decref();
// Reset to original behaviour.
- Prog::TEST_dfa_should_bail_when_slow(true);
+ Prog::TESTING_ONLY_set_dfa_should_bail_when_slow(true);
ASSERT_GT(state_cache_resets, 0);
ASSERT_EQ(search_failures, 0);
}
@@ -218,7 +218,7 @@
}
TEST(Multithreaded, SearchDFA) {
- Prog::TEST_dfa_should_bail_when_slow(false);
+ Prog::TESTING_ONLY_set_dfa_should_bail_when_slow(false);
state_cache_resets = 0;
search_failures = 0;
@@ -259,7 +259,7 @@
re->Decref();
// Reset to original behaviour.
- Prog::TEST_dfa_should_bail_when_slow(true);
+ Prog::TESTING_ONLY_set_dfa_should_bail_when_slow(true);
ASSERT_GT(state_cache_resets, 0);
ASSERT_EQ(search_failures, 0);
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/testing/regexp_benchmark.cc
new/re2-2021-08-01/re2/testing/regexp_benchmark.cc
--- old/re2-2021-06-01/re2/testing/regexp_benchmark.cc 2021-05-21
13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/testing/regexp_benchmark.cc 2021-07-24
13:39:54.000000000 +0200
@@ -181,10 +181,11 @@
state.SetBytesProcessed(state.iterations() * state.range(0));
}
-// These two are easy because they start with an A,
-// giving the search loop something to memchr for.
+// These three are easy because they have prefixes,
+// giving the search loop something to prefix accel.
#define EASY0 "ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
#define EASY1 "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$"
+#define EASY2 "(?i)" EASY0
// This is a little harder, since it starts with a character class
// and thus can't be memchr'ed. Could look for ABC and work backward,
@@ -228,6 +229,18 @@
#endif
BENCHMARK_RANGE(Search_Easy1_CachedRE2, 8, 16<<20)->ThreadRange(1,
NumCPUs());
+void Search_Easy2_CachedDFA(benchmark::State& state) { Search(state,
EASY2, SearchCachedDFA); }
+void Search_Easy2_CachedNFA(benchmark::State& state) { Search(state,
EASY2, SearchCachedNFA); }
+void Search_Easy2_CachedPCRE(benchmark::State& state) { Search(state,
EASY2, SearchCachedPCRE); }
+void Search_Easy2_CachedRE2(benchmark::State& state) { Search(state,
EASY2, SearchCachedRE2); }
+
+BENCHMARK_RANGE(Search_Easy2_CachedDFA, 8, 16<<20)->ThreadRange(1,
NumCPUs());
+BENCHMARK_RANGE(Search_Easy2_CachedNFA, 8, 256<<10)->ThreadRange(1,
NumCPUs());
+#ifdef USEPCRE
+BENCHMARK_RANGE(Search_Easy2_CachedPCRE, 8, 16<<20)->ThreadRange(1,
NumCPUs());
+#endif
+BENCHMARK_RANGE(Search_Easy2_CachedRE2, 8, 16<<20)->ThreadRange(1,
NumCPUs());
+
void Search_Medium_CachedDFA(benchmark::State& state) { Search(state,
MEDIUM, SearchCachedDFA); }
void Search_Medium_CachedNFA(benchmark::State& state) { Search(state,
MEDIUM, SearchCachedNFA); }
void Search_Medium_CachedPCRE(benchmark::State& state) { Search(state,
MEDIUM, SearchCachedPCRE); }
@@ -953,6 +966,8 @@
CHECK(prog);
cache[regexp] = prog;
re->Decref();
+ // We must call this here - while we have exclusive access.
+ prog->IsOnePass();
}
return prog;
}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/re2-2021-06-01/re2/testing/required_prefix_test.cc
new/re2-2021-08-01/re2/testing/required_prefix_test.cc
--- old/re2-2021-06-01/re2/testing/required_prefix_test.cc 2021-05-21
13:25:31.000000000 +0200
+++ new/re2-2021-08-01/re2/testing/required_prefix_test.cc 2021-07-24
13:39:54.000000000 +0200
@@ -131,23 +131,69 @@
}
}
-TEST(PrefixAccel, BasicTest) {
- Regexp* re = Regexp::Parse("abc\\d+", Regexp::LikePerl, NULL);
+TEST(RequiredPrefixForAccel, CaseFoldingForKAndS) {
+ Regexp* re;
+ std::string p;
+ bool f;
+
+ // With Latin-1 encoding, `(?i)` prefixes can include 'k' and 's'.
+ re = Regexp::Parse("(?i)KLM", Regexp::LikePerl|Regexp::Latin1, NULL);
ASSERT_TRUE(re != NULL);
- Prog* prog = re->CompileToProg(0);
- ASSERT_TRUE(prog != NULL);
- for (int i = 0; i < 100; i++) {
- std::string text(i, 'a');
- const char* p = reinterpret_cast<const char*>(
- prog->PrefixAccel(text.data(), text.size()));
- EXPECT_TRUE(p == NULL);
- text.append("abc");
- p = reinterpret_cast<const char*>(
- prog->PrefixAccel(text.data(), text.size()));
- EXPECT_EQ(i, p-text.data());
- }
- delete prog;
+ ASSERT_TRUE(re->RequiredPrefixForAccel(&p, &f));
+ ASSERT_EQ(p, "klm");
+ ASSERT_EQ(f, true);
+ re->Decref();
+
+ re = Regexp::Parse("(?i)STU", Regexp::LikePerl|Regexp::Latin1, NULL);
+ ASSERT_TRUE(re != NULL);
+ ASSERT_TRUE(re->RequiredPrefixForAccel(&p, &f));
+ ASSERT_EQ(p, "stu");
+ ASSERT_EQ(f, true);
+ re->Decref();
+
+ // With UTF-8 encoding, `(?i)` prefixes can't include 'k' and 's'.
+ // This is because they match U+212A and U+017F, respectively, and
+ // so the parser ends up emitting character classes, not literals.
+ re = Regexp::Parse("(?i)KLM", Regexp::LikePerl, NULL);
+ ASSERT_TRUE(re != NULL);
+ ASSERT_FALSE(re->RequiredPrefixForAccel(&p, &f));
re->Decref();
+
+ re = Regexp::Parse("(?i)STU", Regexp::LikePerl, NULL);
+ ASSERT_TRUE(re != NULL);
+ ASSERT_FALSE(re->RequiredPrefixForAccel(&p, &f));
+ re->Decref();
+}
+
+static const char* prefix_accel_tests[] = {
+ "aababc\\d+",
+ "(?i)AABABC\\d+",
+};
+
+TEST(PrefixAccel, SimpleTests) {
+ for (size_t i = 0; i < arraysize(prefix_accel_tests); i++) {
+ const char* pattern = prefix_accel_tests[i];
+ Regexp* re = Regexp::Parse(pattern, Regexp::LikePerl, NULL);
+ ASSERT_TRUE(re != NULL);
+ Prog* prog = re->CompileToProg(0);
+ ASSERT_TRUE(prog != NULL);
+ ASSERT_TRUE(prog->can_prefix_accel());
+ for (int j = 0; j < 100; j++) {
+ std::string text(j, 'a');
+ const char* p = reinterpret_cast<const char*>(
+ prog->PrefixAccel(text.data(), text.size()));
+ EXPECT_TRUE(p == NULL);
+ text.append("aababc");
+ for (int k = 0; k < 100; k++) {
+ text.append(k, 'a');
+ p = reinterpret_cast<const char*>(
+ prog->PrefixAccel(text.data(), text.size()));
+ EXPECT_EQ(j, p - text.data());
+ }
+ }
+ delete prog;
+ re->Decref();
+ }
}
} // namespace re2
