Include RE2 library

third_party/re2/re2/bitstate.cc

+// Copyright 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.
+
+// Tested by search_test.cc, exhaustive_test.cc, tester.cc
+
+// Prog::SearchBitState is a regular expression search with submatch
+// tracking for small regular expressions and texts.  Like
+// testing/backtrack.cc, it allocates a bit vector with (length of
+// text) * (length of prog) bits, to make sure it never explores the
+// same (character position, instruction) state multiple times.  This
+// limits the search to run in time linear in the length of the text.
+//
+// Unlike testing/backtrack.cc, SearchBitState is not recursive
+// on the text.
+//
+// SearchBitState is a fast replacement for the NFA code on small
+// regexps and texts when SearchOnePass cannot be used.
+
+#include "re2/prog.h"
+#include "re2/regexp.h"
+
+namespace re2 {
+
+struct Job {
+  int id;
+  int arg;
+  const char* p;
+};
+
+class BitState {
+ public:
+  explicit BitState(Prog* prog);
+  ~BitState();
+
+  // The usual Search prototype.
+  // Can only call Search once per BitState.
+  bool Search(const StringPiece& text, const StringPiece& context,
+              bool anchored, bool longest,
+              StringPiece* submatch, int nsubmatch);
+
+ private:
+  inline bool ShouldVisit(int id, const char* p);
+  void Push(int id, const char* p, int arg);
+  bool GrowStack();
+  bool TrySearch(int id, const char* p);
+
+  // Search parameters
+  Prog* prog_;              // program being run
+  StringPiece text_;        // text being searched
+  StringPiece context_;     // greater context of text being searched
+  bool anchored_;           // whether search is anchored at text.begin()
+  bool longest_;            // whether search wants leftmost-longest match
+  bool endmatch_;           // whether match must end at text.end()
+  StringPiece *submatch_;   // submatches to fill in
+  int nsubmatch_;           //   # of submatches to fill in
+
+  // Search state
+  const char** cap_;        // capture registers
+  int ncap_;
+
+  static const int VisitedBits = 32;
+  uint32 *visited_;         // bitmap: (Inst*, char*) pairs already backtracked
+  int nvisited_;            //   # of words in bitmap
+
+  Job *job_;                // stack of text positions to explore
+  int njob_;
+  int maxjob_;
+};
+
+BitState::BitState(Prog* prog)
+  : prog_(prog),
+    anchored_(false),
+    longest_(false),
+    endmatch_(false),
+    submatch_(NULL),
+    nsubmatch_(0),
+    cap_(NULL),
+    ncap_(0),
+    visited_(NULL),
+    nvisited_(0),
+    job_(NULL),
+    njob_(0),
+    maxjob_(0) {
+}
+
+BitState::~BitState() {
+  delete[] visited_;
+  delete[] job_;
+  delete[] cap_;
+}
+
+// Should the search visit the pair ip, p?
+// If so, remember that it was visited so that the next time,
+// we don't repeat the visit.
+bool BitState::ShouldVisit(int id, const char* p) {
+  uint n = id * (text_.size() + 1) + (p - text_.begin());
+  if (visited_[n/VisitedBits] & (1 << (n & (VisitedBits-1))))
+    return false;
+  visited_[n/VisitedBits] |= 1 << (n & (VisitedBits-1));
+  return true;
+}
+
+// Grow the stack.
+bool BitState::GrowStack() {
+  // VLOG(0) << "Reallocate.";
+  maxjob_ *= 2;
+  Job* newjob = new Job[maxjob_];
+  memmove(newjob, job_, njob_*sizeof job_[0]);
+  delete[] job_;
+  job_ = newjob;
+  if (njob_ >= maxjob_) {
+    LOG(DFATAL) << "Job stack overflow.";
+    return false;
+  }
+  return true;
+}
+
+// Push the triple (id, p, arg) onto the stack, growing it if necessary.
+void BitState::Push(int id, const char* p, int arg) {
+  if (njob_ >= maxjob_) {
+    if (!GrowStack())
+      return;
+  }
+  int op = prog_->inst(id)->opcode();
+  if (op == kInstFail)
+    return;
+
+  // Only check ShouldVisit when arg == 0.
+  // When arg > 0, we are continuing a previous visit.
+  if (arg == 0 && !ShouldVisit(id, p))
+    return;
+
+  Job* j = &job_[njob_++];
+  j->id = id;
+  j->p = p;
+  j->arg = arg;
+}
+
+// Try a search from instruction id0 in state p0.
+// Return whether it succeeded.
+bool BitState::TrySearch(int id0, const char* p0) {
+  bool matched = false;
+  const char* end = text_.end();
+  njob_ = 0;
+  Push(id0, p0, 0);
+  while (njob_ > 0) {
+    // Pop job off stack.
+    --njob_;
+    int id = job_[njob_].id;
+    const char* p = job_[njob_].p;
+    int arg = job_[njob_].arg;
+
+    // Optimization: rather than push and pop,
+    // code that is going to Push and continue
+    // the loop simply updates ip, p, and arg
+    // and jumps to CheckAndLoop.  We have to
+    // do the ShouldVisit check that Push
+    // would have, but we avoid the stack
+    // manipulation.
+    if (0) {
+    CheckAndLoop:
+      if (!ShouldVisit(id, p))
+        continue;
+    }
+
+    // Visit ip, p.
+    // VLOG(0) << "Job: " << ip->id() << " "
+    //         << (p - text_.begin()) << " " << arg;
+    Prog::Inst* ip = prog_->inst(id);
+    switch (ip->opcode()) {
+      case kInstFail:
+      default:
+        LOG(DFATAL) << "Unexpected opcode: " << ip->opcode() << " arg " << arg;
+        return false;
+
+      case kInstAlt:
+        // Cannot just
+        //   Push(ip->out1(), p, 0);
+        //   Push(ip->out(), p, 0);
+        // If, during the processing of ip->out(), we encounter
+        // ip->out1() via another path, we want to process it then.
+        // Pushing it here will inhibit that.  Instead, re-push
+        // ip with arg==1 as a reminder to push ip->out1() later.
+        switch (arg) {
+          case 0:
+            Push(id, p, 1);  // come back when we're done
+            id = ip->out();
+            goto CheckAndLoop;
+
+          case 1:
+            // Finished ip->out(); try ip->out1().
+            arg = 0;
+            id = ip->out1();
+            goto CheckAndLoop;
+        }
+        LOG(DFATAL) << "Bad arg in kInstCapture: " << arg;
+        continue;
+
+      case kInstAltMatch:
+        // One opcode is byte range; the other leads to match.
+        if (ip->greedy(prog_)) {
+          // out1 is the match
+          Push(ip->out1(), p, 0);
+          id = ip->out1();
+          p = end;
+          goto CheckAndLoop;
+        }
+        // out is the match - non-greedy
+        Push(ip->out(), end, 0);
+        id = ip->out();
+        goto CheckAndLoop;
+
+      case kInstByteRange: {
+        int c = -1;
+        if (p < end)
+          c = *p & 0xFF;
+        if (ip->Matches(c)) {
+          id = ip->out();
+          p++;
+          goto CheckAndLoop;
+        }
+        continue;
+      }
+
+      case kInstCapture:
+        switch (arg) {
+          case 0:
+            if (0 <= ip->cap() && ip->cap() < ncap_) {
+              // Capture p to register, but save old value.
+              Push(id, cap_[ip->cap()], 1);  // come back when we're done
+              cap_[ip->cap()] = p;
+            }
+            // Continue on.
+            id = ip->out();
+            goto CheckAndLoop;
+          case 1:
+            // Finished ip->out(); restore the old value.
+            cap_[ip->cap()] = p;
+            continue;
+        }
+        LOG(DFATAL) << "Bad arg in kInstCapture: " << arg;
+        continue;
+
+      case kInstEmptyWidth:
+        if (ip->empty() & ~Prog::EmptyFlags(context_, p))
+          continue;
+        id = ip->out();
+        goto CheckAndLoop;
+
+      case kInstNop:
+        id = ip->out();
+        goto CheckAndLoop;
+
+      case kInstMatch: {
+        if (endmatch_ && p != text_.end())
+          continue;
+
+        // VLOG(0) << "Found match.";
+        // We found a match.  If the caller doesn't care
+        // where the match is, no point going further.
+        if (nsubmatch_ == 0)
+          return true;
+
+        // Record best match so far.
+        // Only need to check end point, because this entire
+        // call is only considering one start position.
+        matched = true;
+        cap_[1] = p;
+        if (submatch_[0].data() == NULL ||
+            (longest_ && p > submatch_[0].end())) {
+          for (int i = 0; i < nsubmatch_; i++)
+            submatch_[i] = StringPiece(cap_[2*i], cap_[2*i+1] - cap_[2*i]);
+        }
+
+        // If going for first match, we're done.
+        if (!longest_)
+          return true;
+
+        // If we used the entire text, no longer match is possible.
+        if (p == text_.end())
+          return true;
+
+        // Otherwise, continue on in hope of a longer match.
+        continue;
+      }
+    }
+  }
+  return matched;
+}
+
+// Search text (within context) for prog_.
+bool BitState::Search(const StringPiece& text, const StringPiece& context,
+                      bool anchored, bool longest,
+                      StringPiece* submatch, int nsubmatch) {
+  // Search parameters.
+  text_ = text;
+  context_ = context;
+  if (context_.begin() == NULL)
+    context_ = text;
+  if (prog_->anchor_start() && context_.begin() != text.begin())
+    return false;
+  if (prog_->anchor_end() && context_.end() != text.end())
+    return false;
+  anchored_ = anchored || prog_->anchor_start();
+  longest_ = longest || prog_->anchor_end();
+  endmatch_ = prog_->anchor_end();
+  submatch_ = submatch;
+  nsubmatch_ = nsubmatch;
+  for (int i = 0; i < nsubmatch_; i++)
+    submatch_[i] = NULL;
+
+  // Allocate scratch space.
+  nvisited_ = (prog_->size() * (text.size()+1) + VisitedBits-1) / VisitedBits;
+  visited_ = new uint32[nvisited_];
+  memset(visited_, 0, nvisited_*sizeof visited_[0]);
+  // VLOG(0) << "nvisited_ = " << nvisited_;
+
+  ncap_ = 2*nsubmatch;
+  if (ncap_ < 2)
+    ncap_ = 2;
+  cap_ = new const char*[ncap_];
+  memset(cap_, 0, ncap_*sizeof cap_[0]);
+
+  maxjob_ = 256;
+  job_ = new Job[maxjob_];
+
+  // Anchored search must start at text.begin().
+  if (anchored_) {
+    cap_[0] = text.begin();
+    return TrySearch(prog_->start(), text.begin());
+  }
+
+  // Unanchored search, starting from each possible text position.
+  // Notice that we have to try the empty string at the end of
+  // the text, so the loop condition is p <= text.end(), not p < text.end().
+  // This looks like it's quadratic in the size of the text,
+  // but we are not clearing visited_ between calls to TrySearch,
+  // so no work is duplicated and it ends up still being linear.
+  for (const char* p = text.begin(); p <= text.end(); p++) {
+    cap_[0] = p;
+    if (TrySearch(prog_->start(), p))  // Match must be leftmost; done.
+      return true;
+  }
+  return false;
+}
+
+// Bit-state search.
+bool Prog::SearchBitState(const StringPiece& text,
+                          const StringPiece& context,
+                          Anchor anchor,
+                          MatchKind kind,
+                          StringPiece* match,
+                          int nmatch) {
+  // If full match, we ask for an anchored longest match
+  // and then check that match[0] == text.
+  // So make sure match[0] exists.
+  StringPiece sp0;
+  if (kind == kFullMatch) {
+    anchor = kAnchored;
+    if (nmatch < 1) {
+      match = &sp0;
+      nmatch = 1;
+    }
+  }
+
+  // Run the search.
+  BitState b(this);
+  bool anchored = anchor == kAnchored;
+  bool longest = kind != kFirstMatch;
+  if (!b.Search(text, context, anchored, longest, match, nmatch))
+    return false;
+  if (kind == kFullMatch && match[0].end() != text.end())
+    return false;
+  return true;
+}
+
+}  // namespace re2