Add an experimental program fanout computation. Change-Id: I92cc607d40d9370be7eba14fe258c08a6fff91c1 Reviewed-on: https://code-review.googlesource.com/2311 Reviewed-by: Russ Cox <rsc@swtch.com>
diff --git a/re2/nfa.cc b/re2/nfa.cc index b588c7e..57a18fe 100644 --- a/re2/nfa.cc +++ b/re2/nfa.cc
@@ -706,5 +706,52 @@ return true; } -} // namespace re2 +// For each instruction i in the program reachable from the start, compute the +// number of instructions reachable from i by following only empty transitions +// and record that count as fanout[i]. +// +// fanout holds the results and is also the work queue for the outer iteration. +// reachable holds the reached nodes for the inner iteration. +void Prog::Fanout(SparseArray<int>* fanout) { + DCHECK_EQ(fanout->max_size(), size()); + SparseSet reachable(size()); + fanout->clear(); + fanout->set_new(start(), 0); + for (SparseArray<int>::iterator i = fanout->begin(); i != fanout->end(); ++i) { + int* count = &i->second; + reachable.clear(); + reachable.insert(i->index()); + for (SparseSet::iterator j = reachable.begin(); j != reachable.end(); ++j) { + Prog::Inst* ip = inst(*j); + switch (ip->opcode()) { + default: + LOG(DFATAL) << "unhandled " << ip->opcode() << " in Prog::Fanout()"; + break; + case kInstByteRange: + (*count)++; + if (!fanout->has_index(ip->out())) { + fanout->set_new(ip->out(), 0); + } + break; + + case kInstAlt: + case kInstAltMatch: + reachable.insert(ip->out1()); + // fall through + + case kInstCapture: + case kInstEmptyWidth: + case kInstNop: + reachable.insert(ip->out()); + break; + + case kInstMatch: + case kInstFail: + break; + } + } + } +} + +} // namespace re2
diff --git a/re2/prog.h b/re2/prog.h index 64707c3..26c8676 100644 --- a/re2/prog.h +++ b/re2/prog.h
@@ -10,6 +10,7 @@ #define RE2_PROG_H__ #include "util/util.h" +#include "util/sparse_array.h" #include "re2/re2.h" namespace re2 { @@ -329,6 +330,10 @@ // Returns true on success, false on error. bool PossibleMatchRange(string* min, string* max, int maxlen); + // EXPERIMENTAL! SUBJECT TO CHANGE! + // Outputs the program fanout into the given sparse array. + void Fanout(SparseArray<int>* fanout); + // Compiles a collection of regexps to Prog. Each regexp will have // its own Match instruction recording the index in the vector. static Prog* CompileSet(const RE2::Options& options, RE2::Anchor anchor,
diff --git a/re2/re2.cc b/re2/re2.cc index 2283f69..3a2262e 100644 --- a/re2/re2.cc +++ b/re2/re2.cc
@@ -16,6 +16,7 @@ #include "util/atomicops.h" #include "util/util.h" #include "util/flags.h" +#include "util/sparse_array.h" #include "re2/prog.h" #include "re2/regexp.h" @@ -272,6 +273,23 @@ return prog_->size(); } +int RE2::ProgramFanout(map<int, int>* histogram) const { + if (prog_ == NULL) + return -1; + SparseArray<int> fanout(prog_->size()); + prog_->Fanout(&fanout); + histogram->clear(); + for (SparseArray<int>::iterator i = fanout.begin(); i != fanout.end(); ++i) { + // TODO(junyer): Optimise this? + int bucket = 0; + while (1 << bucket < i->second) { + bucket++; + } + (*histogram)[bucket]++; + } + return histogram->rbegin()->first; +} + // Returns named_groups_, computing it if needed. const map<string, int>& RE2::NamedCapturingGroups() const { MutexLock l(mutex_);
diff --git a/re2/re2.h b/re2/re2.h index 85a711f..6bf7ac6 100644 --- a/re2/re2.h +++ b/re2/re2.h
@@ -293,6 +293,11 @@ // Larger numbers are more expensive than smaller numbers. int ProgramSize() const; + // EXPERIMENTAL! SUBJECT TO CHANGE! + // Outputs the program fanout as a histogram bucketed by powers of 2. + // Returns the number of the largest non-empty bucket. + int ProgramFanout(map<int, int>* histogram) const; + // Returns the underlying Regexp; not for general use. // Returns entire_regexp_ so that callers don't need // to know about prefix_ and prefix_foldcase_.
diff --git a/re2/testing/re2_test.cc b/re2/testing/re2_test.cc index efd3a20..8505195 100644 --- a/re2/testing/re2_test.cc +++ b/re2/testing/re2_test.cc
@@ -462,13 +462,38 @@ TEST(ProgramSize, BigProgram) { RE2 re_simple("simple regexp"); RE2 re_medium("medium.*regexp"); - RE2 re_complex("hard.{1,128}regexp"); + RE2 re_complex("complex.{1,128}regexp"); CHECK_GT(re_simple.ProgramSize(), 0); CHECK_GT(re_medium.ProgramSize(), re_simple.ProgramSize()); CHECK_GT(re_complex.ProgramSize(), re_medium.ProgramSize()); } +TEST(ProgramFanout, BigProgram) { + RE2 re1("(?:(?:(?:(?:(?:.)?){1})*)+)"); + RE2 re10("(?:(?:(?:(?:(?:.)?){10})*)+)"); + RE2 re100("(?:(?:(?:(?:(?:.)?){100})*)+)"); + RE2 re1000("(?:(?:(?:(?:(?:.)?){1000})*)+)"); + + map<int, int> histogram; + + // 3 is the largest non-empty bucket and has 1 element. + CHECK_EQ(3, re1.ProgramFanout(&histogram)); + CHECK_EQ(1, histogram[3]); + + // 7 is the largest non-empty bucket and has 10 elements. + CHECK_EQ(7, re10.ProgramFanout(&histogram)); + CHECK_EQ(10, histogram[7]); + + // 10 is the largest non-empty bucket and has 100 elements. + CHECK_EQ(10, re100.ProgramFanout(&histogram)); + CHECK_EQ(100, histogram[10]); + + // 13 is the largest non-empty bucket and has 1000 elements. + CHECK_EQ(13, re1000.ProgramFanout(&histogram)); + CHECK_EQ(1000, histogram[13]); +} + // Issue 956519: handling empty character sets was // causing NULL dereference. This tests a few empty character sets. // (The way to get an empty character set is to negate a full one.)