Include RE2 library

third_party/re2/re2/nfa.cc

+// Copyright 2006-2007 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.
+//
+// Prog::SearchNFA, an NFA search.
+// This is an actual NFA like the theorists talk about,
+// not the pseudo-NFA found in backtracking regexp implementations.
+//
+// IMPLEMENTATION
+//
+// This algorithm is a variant of one that appeared in Rob Pike's sam editor,
+// which is a variant of the one described in Thompson's 1968 CACM paper.
+// See http://swtch.com/~rsc/regexp/ for various history.  The main feature
+// over the DFA implementation is that it tracks submatch boundaries.
+//
+// When the choice of submatch boundaries is ambiguous, this particular
+// implementation makes the same choices that traditional backtracking
+// implementations (in particular, Perl and PCRE) do.
+// Note that unlike in Perl and PCRE, this algorithm *cannot* take exponential
+// time in the length of the input.
+//
+// Like Thompson's original machine and like the DFA implementation, this
+// implementation notices a match only once it is one byte past it.
+
+#include "re2/prog.h"
+#include "re2/regexp.h"
+#include "util/sparse_array.h"
+#include "util/sparse_set.h"
+
+namespace re2 {
+
+class NFA {
+ public:
+  NFA(Prog* prog);
+  ~NFA();
+
+  // Searches for a matching string.
+  //   * If anchored is true, only considers matches starting at offset.
+  //     Otherwise finds lefmost match at or after offset.
+  //   * If longest is true, returns the longest match starting
+  //     at the chosen start point.  Otherwise returns the so-called
+  //     left-biased match, the one traditional backtracking engines
+  //     (like Perl and PCRE) find.
+  // Records submatch boundaries in submatch[1..nsubmatch-1].
+  // Submatch[0] is the entire match.  When there is a choice in
+  // which text matches each subexpression, the submatch boundaries
+  // are chosen to match what a backtracking implementation would choose.
+  bool Search(const StringPiece& text, const StringPiece& context,
+              bool anchored, bool longest,
+              StringPiece* submatch, int nsubmatch);
+
+  static const int Debug = 0;
+
+ private:
+  struct Thread {
+    union {
+      int id;
+      Thread* next;  // when on free list
+    };
+    const char** capture;
+  };
+
+  // State for explicit stack in AddToThreadq.
+  struct AddState {
+    int id;           // Inst to process
+    int j;
+    const char* cap_j;  // if j>=0, set capture[j] = cap_j before processing ip
+
+    AddState()
+      : id(0), j(-1), cap_j(NULL) {}
+    explicit AddState(int id)
+      : id(id), j(-1), cap_j(NULL) {}
+    AddState(int id, const char* cap_j, int j)
+      : id(id), j(j), cap_j(cap_j) {}
+  };
+
+  // Threadq is a list of threads.  The list is sorted by the order
+  // in which Perl would explore that particular state -- the earlier
+  // choices appear earlier in the list.
+  typedef SparseArray<Thread*> Threadq;
+
+  inline Thread* AllocThread();
+  inline void FreeThread(Thread*);
+
+  // Add id (or its children, following unlabeled arrows)
+  // to the workqueue q with associated capture info.
+  void AddToThreadq(Threadq* q, int id, int flag,
+                    const char* p, const char** capture);
+
+  // Run runq on byte c, appending new states to nextq.
+  // Updates matched_ and match_ as new, better matches are found.
+  // p is position of the next byte (the one after c)
+  // in the input string, used when processing capturing parens.
+  // flag is the bitwise or of Bol, Eol, etc., specifying whether
+  // ^, $ and \b match the current input point (after c).
+  inline int Step(Threadq* runq, Threadq* nextq, int c, int flag, const char* p);
+
+  // Returns text version of capture information, for debugging.
+  string FormatCapture(const char** capture);
+
+  inline void CopyCapture(const char** dst, const char** src);
+
+  // Computes whether all matches must begin with the same first
+  // byte, and if so, returns that byte.  If not, returns -1.
+  int ComputeFirstByte();
+
+  Prog* prog_;          // underlying program
+  int start_;           // start instruction in program
+  int ncapture_;        // number of submatches to track
+  bool longest_;        // whether searching for longest match
+  bool endmatch_;       // whether match must end at text.end()
+  const char* btext_;   // beginning of text being matched (for FormatSubmatch)
+  const char* etext_;   // end of text being matched (for endmatch_)
+  Threadq q0_, q1_;     // pre-allocated for Search.
+  const char** match_;  // best match so far
+  bool matched_;        // any match so far?
+  AddState* astack_;    // pre-allocated for AddToThreadq
+  int nastack_;
+  int first_byte_;      // required first byte for match, or -1 if none
+
+  Thread* free_threads_;  // free list
+
+  DISALLOW_EVIL_CONSTRUCTORS(NFA);
+};
+
+NFA::NFA(Prog* prog) {
+  prog_ = prog;
+  start_ = prog->start();
+  ncapture_ = 0;
+  longest_ = false;
+  endmatch_ = false;
+  btext_ = NULL;
+  etext_ = NULL;
+  q0_.resize(prog_->size());
+  q1_.resize(prog_->size());
+  nastack_ = 2*prog_->size();
+  astack_ = new AddState[nastack_];
+  match_ = NULL;
+  matched_ = false;
+  free_threads_ = NULL;
+  first_byte_ = ComputeFirstByte();
+}
+
+NFA::~NFA() {
+  delete[] match_;
+  delete[] astack_;
+  Thread* next;
+  for (Thread* t = free_threads_; t; t = next) {
+    next = t->next;
+    delete[] t->capture;
+    delete t;
+  }
+}
+
+void NFA::FreeThread(Thread *t) {
+  if (t == NULL)
+    return;
+  t->next = free_threads_;
+  free_threads_ = t;
+}
+
+NFA::Thread* NFA::AllocThread() {
+  Thread* t = free_threads_;
+  if (t == NULL) {
+    t = new Thread;
+    t->capture = new const char*[ncapture_];
+    return t;
+  }
+  free_threads_ = t->next;
+  return t;
+}
+
+void NFA::CopyCapture(const char** dst, const char** src) {
+  for (int i = 0; i < ncapture_; i+=2) {
+    dst[i] = src[i];
+    dst[i+1] = src[i+1];
+  }
+}
+
+// Follows all empty arrows from id0 and enqueues all the states reached.
+// The bits in flag (Bol, Eol, etc.) specify whether ^, $ and \b match.
+// The pointer p is the current input position, and m is the
+// current set of match boundaries.
+void NFA::AddToThreadq(Threadq* q, int id0, int flag,
+                       const char* p, const char** capture) {
+  if (id0 == 0)
+    return;
+
+  // Astack_ is pre-allocated to avoid resize operations.
+  // It has room for 2*prog_->size() entries, which is enough:
+  // Each inst in prog can be processed at most once,
+  // pushing at most two entries on stk.
+
+  int nstk = 0;
+  AddState* stk = astack_;
+  stk[nstk++] = AddState(id0);
+
+  while (nstk > 0) {
+    DCHECK_LE(nstk, nastack_);
+    const AddState& a = stk[--nstk];
+    if (a.j >= 0)
+      capture[a.j] = a.cap_j;
+
+    int id = a.id;
+    if (id == 0)
+      continue;
+    if (q->has_index(id)) {
+      if (Debug)
+        fprintf(stderr, "  [%d%s]\n", id, FormatCapture(capture).c_str());
+      continue;
+    }
+
+    // Create entry in q no matter what.  We might fill it in below,
+    // or we might not.  Even if not, it is necessary to have it,
+    // so that we don't revisit id0 during the recursion.
+    q->set_new(id, NULL);
+
+    Thread** tp = &q->find(id)->second;
+    int j;
+    Thread* t;
+    Prog::Inst* ip = prog_->inst(id);
+    switch (ip->opcode()) {
+    default:
+      LOG(DFATAL) << "unhandled " << ip->opcode() << " in AddToThreadq";
+      break;
+
+    case kInstFail:
+      break;
+
+    case kInstAltMatch:
+      // Save state; will pick up at next byte.
+      t = AllocThread();
+      t->id = id;
+      CopyCapture(t->capture, capture);
+      *tp = t;
+      // fall through
+
+    case kInstAlt:
+      // Explore alternatives.
+      stk[nstk++] = AddState(ip->out1());
+      stk[nstk++] = AddState(ip->out());
+      break;
+
+    case kInstNop:
+      // Continue on.
+      stk[nstk++] = AddState(ip->out());
+      break;
+
+    case kInstCapture:
+      if ((j=ip->cap()) < ncapture_) {
+        // Push a dummy whose only job is to restore capture[j]
+        // once we finish exploring this possibility.
+        stk[nstk++] = AddState(0, capture[j], j);
+
+        // Record capture.
+        capture[j] = p;
+      }
+      stk[nstk++] = AddState(ip->out());
+      break;
+
+    case kInstMatch:
+    case kInstByteRange:
+      // Save state; will pick up at next byte.
+      t = AllocThread();
+      t->id = id;
+      CopyCapture(t->capture, capture);
+      *tp = t;
+      if (Debug)
+        fprintf(stderr, " + %d%s [%p]\n", id, FormatCapture(t->capture).c_str(), t);
+      break;
+
+    case kInstEmptyWidth:
+      // Continue on if we have all the right flag bits.
+      if (ip->empty() & ~flag)
+        break;
+      stk[nstk++] = AddState(ip->out());
+      break;
+    }
+  }
+}
+
+// Run runq on byte c, appending new states to nextq.
+// Updates match as new, better matches are found.
+// p is position of the byte c in the input string,
+// used when processing capturing parens.
+// flag is the bitwise or of Bol, Eol, etc., specifying whether
+// ^, $ and \b match the current input point (after c).
+// Frees all the threads on runq.
+// If there is a shortcut to the end, returns that shortcut.
+int NFA::Step(Threadq* runq, Threadq* nextq, int c, int flag, const char* p) {
+  nextq->clear();
+
+  for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) {
+    Thread* t = i->second;
+    if (t == NULL)
+      continue;
+
+    if (longest_) {
+      // Can skip any threads started after our current best match.
+      if (matched_ && match_[0] < t->capture[0]) {
+        FreeThread(t);
+        continue;
+      }
+    }
+
+    int id = t->id;
+    Prog::Inst* ip = prog_->inst(id);
+
+    switch (ip->opcode()) {
+      default:
+        // Should only see the values handled below.
+        LOG(DFATAL) << "Unhandled " << ip->opcode() << " in step";
+        break;
+
+      case kInstByteRange:
+        if (ip->Matches(c))
+          AddToThreadq(nextq, ip->out(), flag, p+1, t->capture);
+        break;
+
+      case kInstAltMatch:
+        if (i != runq->begin())
+          break;
+        // The match is ours if we want it.
+        if (ip->greedy(prog_) || longest_) {
+          CopyCapture((const char**)match_, t->capture);
+          FreeThread(t);
+          for (++i; i != runq->end(); ++i)
+            FreeThread(i->second);
+          runq->clear();
+          matched_ = true;
+          if (ip->greedy(prog_))
+            return ip->out1();
+          return ip->out();
+        }
+        break;
+
+      case kInstMatch:
+        if (endmatch_ && p != etext_)
+          break;
+
+        const char* old = t->capture[1];  // previous end pointer
+        t->capture[1] = p;
+        if (longest_) {
+          // Leftmost-longest mode: save this match only if
+          // it is either farther to the left or at the same
+          // point but longer than an existing match.
+          if (!matched_ || t->capture[0] < match_[0] ||
+              (t->capture[0] == match_[0] && t->capture[1] > match_[1]))
+            CopyCapture((const char**)match_, t->capture);
+        } else {
+          // Leftmost-biased mode: this match is by definition
+          // better than what we've already found (see next line).
+          CopyCapture((const char**)match_, t->capture);
+
+          // Cut off the threads that can only find matches
+          // worse than the one we just found: don't run the
+          // rest of the current Threadq.
+          t->capture[0] = old;
+          FreeThread(t);
+          for (++i; i != runq->end(); ++i)
+            FreeThread(i->second);
+          runq->clear();
+          matched_ = true;
+          return 0;
+        }
+        t->capture[0] = old;
+        matched_ = true;
+        break;
+    }
+    FreeThread(t);
+  }
+  runq->clear();
+  return 0;
+}
+
+string NFA::FormatCapture(const char** capture) {
+  string s;
+
+  for (int i = 0; i < ncapture_; i+=2) {
+    if (capture[i] == NULL)
+      StringAppendF(&s, "(?,?)");
+    else if (capture[i+1] == NULL)
+      StringAppendF(&s, "(%d,?)", (int)(capture[i] - btext_));
+    else
+      StringAppendF(&s, "(%d,%d)",
+                    (int)(capture[i] - btext_),
+                    (int)(capture[i+1] - btext_));
+  }
+  return s;
+}
+
+// Returns whether haystack contains needle's memory.
+static bool StringPieceContains(const StringPiece haystack, const StringPiece needle) {
+  return haystack.begin() <= needle.begin() &&
+         haystack.end() >= needle.end();
+}
+
+bool NFA::Search(const StringPiece& text, const StringPiece& const_context,
+            bool anchored, bool longest,
+            StringPiece* submatch, int nsubmatch) {
+  if (start_ == 0)
+    return false;
+
+  StringPiece context = const_context;
+  if (context.begin() == NULL)
+    context = text;
+
+  if (!StringPieceContains(context, text)) {
+    LOG(FATAL) << "Bad args: context does not contain text "
+                << reinterpret_cast<const void*>(context.begin())
+                << "+" << context.size() << " "
+                << reinterpret_cast<const void*>(text.begin())
+                << "+" << text.size();
+    return false;
+  }
+
+  if (prog_->anchor_start() && context.begin() != text.begin())
+    return false;
+  if (prog_->anchor_end() && context.end() != text.end())
+    return false;
+  anchored |= prog_->anchor_start();
+  if (prog_->anchor_end()) {
+    longest = true;
+    endmatch_ = true;
+    etext_ = text.end();
+  }
+
+  if (nsubmatch < 0) {
+    LOG(DFATAL) << "Bad args: nsubmatch=" << nsubmatch;
+    return false;
+  }
+
+  // Save search parameters.
+  ncapture_ = 2*nsubmatch;
+  longest_ = longest;
+
+  if (nsubmatch == 0) {
+    // We need to maintain match[0], both to distinguish the
+    // longest match (if longest is true) and also to tell
+    // whether we've seen any matches at all.
+    ncapture_ = 2;
+  }
+
+  match_ = new const char*[ncapture_];
+  matched_ = false;
+  memset(match_, 0, ncapture_*sizeof match_[0]);
+
+  // For debugging prints.
+  btext_ = context.begin();
+
+  if (Debug) {
+    fprintf(stderr, "NFA::Search %s (context: %s) anchored=%d longest=%d\n",
+            text.as_string().c_str(), context.as_string().c_str(), anchored,
+            longest);
+  }
+
+  // Set up search.
+  Threadq* runq = &q0_;
+  Threadq* nextq = &q1_;
+  runq->clear();
+  nextq->clear();
+  memset(&match_[0], 0, ncapture_*sizeof match_[0]);
+  const char* bp = context.begin();
+  int c = -1;
+  int wasword = 0;
+
+  if (text.begin() > context.begin()) {
+    c = text.begin()[-1] & 0xFF;
+    wasword = Prog::IsWordChar(c);
+  }
+
+  // Loop over the text, stepping the machine.
+  for (const char* p = text.begin();; p++) {
+    // Check for empty-width specials.
+    int flag = 0;
+
+    // ^ and \A
+    if (p == context.begin())
+      flag |= kEmptyBeginText | kEmptyBeginLine;
+    else if (p <= context.end() && p[-1] == '\n')
+      flag |= kEmptyBeginLine;
+
+    // $ and \z
+    if (p == context.end())
+      flag |= kEmptyEndText | kEmptyEndLine;
+    else if (p < context.end() && p[0] == '\n')
+      flag |= kEmptyEndLine;
+
+    // \b and \B
+    int isword = 0;
+    if (p < context.end())
+      isword = Prog::IsWordChar(p[0] & 0xFF);
+
+    if (isword != wasword)
+      flag |= kEmptyWordBoundary;
+    else
+      flag |= kEmptyNonWordBoundary;
+
+    if (Debug) {
+      fprintf(stderr, "%c[%#x/%d/%d]:", p > text.end() ? '$' : p == bp ? '^' : c, flag, isword, wasword);
+      for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) {
+        Thread* t = i->second;
+        if (t == NULL)
+          continue;
+        fprintf(stderr, " %d%s", t->id,
+                FormatCapture((const char**)t->capture).c_str());
+      }
+      fprintf(stderr, "\n");
+    }
+
+    // Process previous character (waited until now to avoid
+    // repeating the flag computation above).
+    // This is a no-op the first time around the loop, because
+    // runq is empty.
+    int id = Step(runq, nextq, c, flag, p-1);
+    DCHECK_EQ(runq->size(), 0);
+    swap(nextq, runq);
+    nextq->clear();
+    if (id != 0) {
+      // We're done: full match ahead.
+      p = text.end();
+      for (;;) {
+        Prog::Inst* ip = prog_->inst(id);
+        switch (ip->opcode()) {
+          default:
+            LOG(DFATAL) << "Unexpected opcode in short circuit: " << ip->opcode();
+            break;
+
+          case kInstCapture:
+            match_[ip->cap()] = p;
+            id = ip->out();
+            continue;
+
+          case kInstNop:
+            id = ip->out();
+            continue;
+
+          case kInstMatch:
+            match_[1] = p;
+            matched_ = true;
+            break;
+
+          case kInstEmptyWidth:
+            if (ip->empty() & ~(kEmptyEndLine|kEmptyEndText)) {
+              LOG(DFATAL) << "Unexpected empty-width in short circuit: " << ip->empty();
+              break;
+            }
+            id = ip->out();
+            continue;
+        }
+        break;
+      }
+      break;
+    }
+
+    if (p > text.end())
+      break;
+
+    // Start a new thread if there have not been any matches.
+    // (No point in starting a new thread if there have been
+    // matches, since it would be to the right of the match
+    // we already found.)
+    if (!matched_ && (!anchored || p == text.begin())) {
+      // If there's a required first byte for an unanchored search
+      // and we're not in the middle of any possible matches,
+      // use memchr to search for the byte quickly.
+      if (!anchored && first_byte_ >= 0 && runq->size() == 0 &&
+          p < text.end() && (p[0] & 0xFF) != first_byte_) {
+        p = reinterpret_cast<const char*>(memchr(p, first_byte_,
+                                                 text.end() - p));
+        if (p == NULL) {
+          p = text.end();
+          isword = 0;
+        } else {
+          isword = Prog::IsWordChar(p[0] & 0xFF);
+        }
+        flag = Prog::EmptyFlags(context, p);
+      }
+
+      // Steal match storage (cleared but unused as of yet)
+      // temporarily to hold match boundaries for new thread.
+      match_[0] = p;
+      AddToThreadq(runq, start_, flag, p, match_);
+      match_[0] = NULL;
+    }
+
+    // If all the threads have died, stop early.
+    if (runq->size() == 0) {
+      if (Debug)
+        fprintf(stderr, "dead\n");
+      break;
+    }
+
+    if (p == text.end())
+      c = 0;
+    else
+      c = *p & 0xFF;
+    wasword = isword;
+
+    // Will run step(runq, nextq, c, ...) on next iteration.  See above.
+  }
+
+  for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i)
+    FreeThread(i->second);
+
+  if (matched_) {
+    for (int i = 0; i < nsubmatch; i++)
+      submatch[i].set(match_[2*i], match_[2*i+1] - match_[2*i]);
+    if (Debug)
+      fprintf(stderr, "match (%d,%d)\n",
+              static_cast<int>(match_[0] - btext_),
+              static_cast<int>(match_[1] - btext_));
+    return true;
+  }
+  VLOG(1) << "No matches found";
+  return false;
+}
+
+// Computes whether all successful matches have a common first byte,
+// and if so, returns that byte.  If not, returns -1.
+int NFA::ComputeFirstByte() {
+  if (start_ == 0)
+    return -1;
+
+  int b = -1;  // first byte, not yet computed
+
+  typedef SparseSet Workq;
+  Workq q(prog_->size());
+  q.insert(start_);
+  for (Workq::iterator it = q.begin(); it != q.end(); ++it) {
+    int id = *it;
+    Prog::Inst* ip = prog_->inst(id);
+    switch (ip->opcode()) {
+      default:
+        LOG(DFATAL) << "unhandled " << ip->opcode() << " in ComputeFirstByte";
+        break;
+
+      case kInstMatch:
+        // The empty string matches: no first byte.
+        return -1;
+
+      case kInstByteRange:
+        // Must match only a single byte
+        if (ip->lo() != ip->hi())
+          return -1;
+        if (ip->foldcase() && 'a' <= ip->lo() && ip->lo() <= 'z')
+          return -1;
+        // If we haven't seen any bytes yet, record it;
+        // otherwise must match the one we saw before.
+        if (b == -1)
+          b = ip->lo();
+        else if (b != ip->lo())
+          return -1;
+        break;
+
+      case kInstNop:
+      case kInstCapture:
+      case kInstEmptyWidth:
+        // Continue on.
+        // Ignore ip->empty() flags for kInstEmptyWidth
+        // in order to be as conservative as possible
+        // (assume all possible empty-width flags are true).
+        if (ip->out())
+          q.insert(ip->out());
+        break;
+
+      case kInstAlt:
+      case kInstAltMatch:
+        // Explore alternatives.
+        if (ip->out())
+          q.insert(ip->out());
+        if (ip->out1())
+          q.insert(ip->out1());
+        break;
+
+      case kInstFail:
+        break;
+    }
+  }
+  return b;
+}
+
+bool
+Prog::SearchNFA(const StringPiece& text, const StringPiece& context,
+                Anchor anchor, MatchKind kind,
+                StringPiece* match, int nmatch) {
+  if (NFA::Debug)
+    Dump();
+
+  NFA nfa(this);
+  StringPiece sp;
+  if (kind == kFullMatch) {
+    anchor = kAnchored;
+    if (nmatch == 0) {
+      match = &sp;
+      nmatch = 1;
+    }
+  }
+  if (!nfa.Search(text, context, anchor == kAnchored, kind != kFirstMatch, match, nmatch))
+    return false;
+  if (kind == kFullMatch && match[0].end() != text.end())
+    return false;
+  return true;
+}
+
+}  // namespace re2
+