commit 749d64c35e09849045303c3de4e9955597b75b53
author Paul Wankadia <junyer@google.com> Mon Nov 05 21:13:23 2018 -0800
committer Paul Wankadia <junyer@google.com> Tue Nov 06 05:14:37 2018 +0000
tree 608dc26147d716e06e9cfd1f49aaa6d3698ea235
parent 169debd6d2b6ebe1d9ff5256e6186082ded1e668

Optimise the check for large substrings.

Change-Id: Ia59b080b5f96e8b31dab221c483f7ed54843a319
Reviewed-on: https://code-review.googlesource.com/c/35272
Reviewed-by: Paul Wankadia <junyer@google.com>

re2/fuzzing/re2_fuzzer.cc

diff --git a/re2/fuzzing/re2_fuzzer.cc b/re2/fuzzing/re2_fuzzer.cc
index abc504b..28ccaf4 100644
--- a/re2/fuzzing/re2_fuzzer.cc
+++ b/re2/fuzzing/re2_fuzzer.cc
@@ -5,10 +5,11 @@
 #include <stddef.h>
 #include <stdint.h>
 #include <map>
+#include <memory>
+#include <queue>
 #include <string>
 
 #include "re2/prefilter.h"
-#include "re2/prefilter_tree.h"
 #include "re2/re2.h"
 
 using re2::StringPiece;
@@ -45,20 +46,22 @@
   // They can cause bug reports due to fuzzer timeouts when they
   // are repetitions (e.g. hundreds of NUL bytes) and matching is
   // unanchored. And they aren't interesting for fuzzing purposes.
-  // Prefilter and PrefilterTree are used because FilteredRE2 will
-  // compile its own RE2 object, which would be a waste of effort.
-  // min_atom_len is as small as possible in order to avoid losing
-  // atoms, which happens when AND/OR nodes are not worth keeping.
-  re2::PrefilterTree prefilter_tree(/*min_atom_len=*/1);
-  re2::Prefilter* prefilter = re2::Prefilter::FromRE2(&re);
-  if (prefilter == NULL)
+  std::unique_ptr<re2::Prefilter> prefilter(re2::Prefilter::FromRE2(&re));
+  if (prefilter == nullptr)
     return;
-  prefilter_tree.Add(prefilter);  // takes ownership
-  std::vector<string> atoms;
-  prefilter_tree.Compile(&atoms);
-  for (const string& atom : atoms) {
-    if (atom.size() > 9)
-      return;
+  std::queue<re2::Prefilter*> nodes;
+  nodes.push(prefilter.get());
+  while (!nodes.empty()) {
+    re2::Prefilter* node = nodes.front();
+    nodes.pop();
+    if (node->op() == re2::Prefilter::ATOM) {
+      if (node->atom().size() > 9)
+        return;
+    } else if (node->op() == re2::Prefilter::AND ||
+               node->op() == re2::Prefilter::OR) {
+      for (re2::Prefilter* sub : *node->subs())
+        nodes.push(sub);
+    }
   }
 
   StringPiece sp1, sp2, sp3, sp4;