re2/nfa.cc - platform/external/regex-re2 - Git at Google

 // 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
	// 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_[2i], match_[2i+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