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