re2/testing/dfa_test.cc

// Copyright 2006-2008 The RE2 Authors.  All Rights Reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

#include "util/test.h"
#include "util/thread.h"
#include "re2/prog.h"
#include "re2/re2.h"
#include "re2/regexp.h"
#include "re2/testing/regexp_generator.h"
#include "re2/testing/string_generator.h"

DECLARE_bool(re2_dfa_bail_when_slow);

DEFINE_int32(size, 8, "log2(number of DFA nodes)");
DEFINE_int32(repeat, 2, "Repetition count.");
DEFINE_int32(threads, 4, "number of threads");

namespace re2 {

// Check that multithreaded access to DFA class works.

// Helper thread: builds entire DFA for prog.
class BuildThread : public Thread {
 public:
  BuildThread(Prog* prog) : prog_(prog) {}
  virtual void Run() {
    CHECK(prog_->BuildEntireDFA(Prog::kFirstMatch));
  }

 private:
  Prog* prog_;
};

TEST(Multithreaded, BuildEntireDFA) {
  // Create regexp with 2^FLAGS_size states in DFA.
  string s = "a";
  for (int i = 0; i < FLAGS_size; i++)
    s += "[ab]";
  s += "b";

  // Check that single-threaded code works.
  {
    //LOG(INFO) << s;
    Regexp* re = Regexp::Parse(s.c_str(), Regexp::LikePerl, NULL);
    CHECK(re);
    Prog* prog = re->CompileToProg(0);
    CHECK(prog);
    BuildThread* t = new BuildThread(prog);
    t->SetJoinable(true);
    t->Start();
    t->Join();
    delete t;
    delete prog;
    re->Decref();
  }

  // Build the DFA simultaneously in a bunch of threads.
  for (int i = 0; i < FLAGS_repeat; i++) {
    Regexp* re = Regexp::Parse(s.c_str(), Regexp::LikePerl, NULL);
    CHECK(re);
    Prog* prog = re->CompileToProg(0);
    CHECK(prog);

    vector<BuildThread*> threads;
    for (int j = 0; j < FLAGS_threads; j++) {
      BuildThread *t = new BuildThread(prog);
      t->SetJoinable(true);
      threads.push_back(t);
    }
    for (int j = 0; j < FLAGS_threads; j++)
      threads[j]->Start();
    for (int j = 0; j < FLAGS_threads; j++) {
      threads[j]->Join();
      delete threads[j];
    }

    // One more compile, to make sure everything is okay.
    prog->BuildEntireDFA(Prog::kFirstMatch);
    delete prog;
    re->Decref();
  }
}

// Check that DFA size requirements are followed.
// BuildEntireDFA will, like SearchDFA, stop building out
// the DFA once the memory limits are reached.
TEST(SingleThreaded, BuildEntireDFA) {
  // Create regexp with 2^30 states in DFA.
  string s = "a";
  for (int i = 0; i < 30; i++)
    s += "[ab]";
  s += "b";

  //LOG(INFO) << s;
  Regexp* re = Regexp::Parse(s.c_str(), Regexp::LikePerl, NULL);
  CHECK(re);
  int max = 24;
  for (int i = 17; i < max; i++) {
    int limit = 1<<i;
    int usage;
    //int progusage, dfamem;
    {
      testing::MallocCounter m(testing::MallocCounter::THIS_THREAD_ONLY);
      Prog* prog = re->CompileToProg(limit);
      CHECK(prog);
      //progusage = m.HeapGrowth();
      //dfamem = prog->dfa_mem();
      prog->BuildEntireDFA(Prog::kFirstMatch);
      prog->BuildEntireDFA(Prog::kLongestMatch);
      usage = m.HeapGrowth();
      delete prog;
    }
    if (!UsingMallocCounter)
      continue;
    //LOG(INFO) << StringPrintf("Limit %d: prog used %d, DFA budget %d, total %d\n",
    //                          limit, progusage, dfamem, usage);
    CHECK_GT(usage, limit*9/10);
    CHECK_LT(usage, limit + (16<<10));  // 16kB of slop okay
  }
  re->Decref();
}

// Generates and returns a string over binary alphabet {0,1} that contains
// all possible binary sequences of length n as subsequences.  The obvious
// brute force method would generate a string of length n * 2^n, but this
// generates a string of length n + 2^n - 1 called a De Bruijn cycle.
// See Knuth, The Art of Computer Programming, Vol 2, Exercise 3.2.2 #17.
// Such a string is useful for testing a DFA.  If you have a DFA
// where distinct last n bytes implies distinct states, then running on a
// DeBruijn string causes the DFA to need to create a new state at every
// position in the input, never reusing any states until it gets to the
// end of the string.  This is the worst possible case for DFA execution.
static string DeBruijnString(int n) {
  CHECK_LT(n, 8*sizeof(int));
  CHECK_GT(n, 0);

  vector<bool> did(1<<n);
  for (int i = 0; i < 1<<n; i++)
    did[i] = false;

  string s;
  for (int i = 0; i < n-1; i++)
    s.append("0");
  int bits = 0;
  int mask = (1<<n) - 1;
  for (int i = 0; i < (1<<n); i++) {
    bits <<= 1;
    bits &= mask;
    if (!did[bits|1]) {
      bits |= 1;
      s.append("1");
    } else {
      s.append("0");
    }
    CHECK(!did[bits]);
    did[bits] = true;
  }
  return s;
}

// Test that the DFA gets the right result even if it runs
// out of memory during a search.  The regular expression
// 0[01]{n}$ matches a binary string of 0s and 1s only if
// the (n+1)th-to-last character is a 0.  Matching this in
// a single forward pass (as done by the DFA) requires
// keeping one bit for each of the last n+1 characters
// (whether each was a 0), or 2^(n+1) possible states.
// If we run this regexp to search in a string that contains
// every possible n-character binary string as a substring,
// then it will have to run through at least 2^n states.
// States are big data structures -- certainly more than 1 byte --
// so if the DFA can search correctly while staying within a
// 2^n byte limit, it must be handling out-of-memory conditions
// gracefully.
TEST(SingleThreaded, SearchDFA) {
  // Choice of n is mostly arbitrary, except that:
  //   * making n too big makes the test run for too long.
  //   * making n too small makes the DFA refuse to run,
  //     because it has so little memory compared to the program size.
  // Empirically, n = 18 is a good compromise between the two.
  const int n = 18;

  Regexp* re = Regexp::Parse(StringPrintf("0[01]{%d}$", n),
                             Regexp::LikePerl, NULL);
  CHECK(re);

  // The De Bruijn string for n ends with a 1 followed by n 0s in a row,
  // which is not a match for 0[01]{n}$.  Adding one more 0 is a match.
  string no_match = DeBruijnString(n);
  string match = no_match + "0";

  // The De Bruijn string is the worst case input for this regexp.
  // By default, the DFA will notice that it is flushing its cache
  // too frequently and will bail out early, so that RE2 can use the
  // 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.
  FLAGS_re2_dfa_bail_when_slow = false;

  int64 usage;
  int64 peak_usage;
  {
    testing::MallocCounter m(testing::MallocCounter::THIS_THREAD_ONLY);
    Prog* prog = re->CompileToProg(1<<n);
    CHECK(prog);
    for (int i = 0; i < 10; i++) {
      bool matched, failed = false;
      matched = prog->SearchDFA(match, NULL,
                                Prog::kUnanchored, Prog::kFirstMatch,
                                NULL, &failed, NULL);
      CHECK(!failed);
      CHECK(matched);
      matched = prog->SearchDFA(no_match, NULL,
                                Prog::kUnanchored, Prog::kFirstMatch,
                                NULL, &failed, NULL);
      CHECK(!failed);
      CHECK(!matched);
    }
    usage = m.HeapGrowth();
    peak_usage = m.PeakHeapGrowth();
    delete prog;
  }
  re->Decref();

  if (!UsingMallocCounter)
    return;
  //LOG(INFO) << "usage " << usage << " " << peak_usage;
  CHECK_LT(usage, 1<<n);
  CHECK_LT(peak_usage, 1<<n);
}

// Helper thread: searches for match, which should match,
// and no_match, which should not.
class SearchThread : public Thread {
 public:
  SearchThread(Prog* prog, const StringPiece& match,
               const StringPiece& no_match)
    : prog_(prog), match_(match), no_match_(no_match) {}

  virtual void Run() {
    for (int i = 0; i < 2; i++) {
      bool matched, failed = false;
      matched = prog_->SearchDFA(match_, NULL,
                                 Prog::kUnanchored, Prog::kFirstMatch,
                                 NULL, &failed, NULL);
      CHECK(!failed);
      CHECK(matched);
      matched = prog_->SearchDFA(no_match_, NULL,
                                 Prog::kUnanchored, Prog::kFirstMatch,
                                 NULL, &failed, NULL);
      CHECK(!failed);
      CHECK(!matched);
    }
  }

 private:
  Prog* prog_;
  StringPiece match_;
  StringPiece no_match_;
};

TEST(Multithreaded, SearchDFA) {
  // Same as single-threaded test above.
  const int n = 18;
  Regexp* re = Regexp::Parse(StringPrintf("0[01]{%d}$", n),
                             Regexp::LikePerl, NULL);
  CHECK(re);
  string no_match = DeBruijnString(n);
  string match = no_match + "0";
  FLAGS_re2_dfa_bail_when_slow = false;

  // Check that single-threaded code works.
  {
    Prog* prog = re->CompileToProg(1<<n);
    CHECK(prog);
    SearchThread* t = new SearchThread(prog, match, no_match);
    t->SetJoinable(true);
    t->Start();
    t->Join();
    delete t;
    delete prog;
  }

  // Run the search simultaneously in a bunch of threads.
  // Reuse same flags for Multithreaded.BuildDFA above.
  for (int i = 0; i < FLAGS_repeat; i++) {
    //LOG(INFO) << "Search " << i;
    Prog* prog = re->CompileToProg(1<<n);
    CHECK(prog);

    vector<SearchThread*> threads;
    for (int j = 0; j < FLAGS_threads; j++) {
      SearchThread *t = new SearchThread(prog, match, no_match);
      t->SetJoinable(true);
      threads.push_back(t);
    }
    for (int j = 0; j < FLAGS_threads; j++)
      threads[j]->Start();
    for (int j = 0; j < FLAGS_threads; j++) {
      threads[j]->Join();
      delete threads[j];
    }
    delete prog;
  }
  re->Decref();
}

struct ReverseTest {
  const char *regexp;
  const char *text;
  bool match;
};

// Test that reverse DFA handles anchored/unanchored correctly.
// It's in the DFA interface but not used by RE2.
ReverseTest reverse_tests[] = {
  { "\\A(a|b)", "abc", true },
  { "(a|b)\\z", "cba", true },
  { "\\A(a|b)", "cba", false },
  { "(a|b)\\z", "abc", false },
};

TEST(DFA, ReverseMatch) {
  int nfail = 0;
  for (int i = 0; i < arraysize(reverse_tests); i++) {
    const ReverseTest& t = reverse_tests[i];
    Regexp* re = Regexp::Parse(t.regexp, Regexp::LikePerl, NULL);
    CHECK(re);
    Prog *prog = re->CompileToReverseProg(0);
    CHECK(prog);
    bool failed = false;
    bool matched = prog->SearchDFA(t.text, NULL, Prog::kUnanchored, Prog::kFirstMatch, NULL, &failed, NULL);
    if (matched != t.match) {
      LOG(ERROR) << t.regexp << " on " << t.text << ": want " << t.match;
      nfail++;
    }
    delete prog;
    re->Decref();
  }
  EXPECT_EQ(nfail, 0);
}

}  // namespace re2