// 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 <stdio.h>

#include <string.h>

#include <algorithm>

#include <deque>

#include <string>

#include <utility>

#include <vector>

#include "util/logging.h"

#include "util/strutil.h"

#include "re2/pod_array.h"

#include "re2/prog.h"

#include "re2/regexp.h"

#include "re2/sparse_array.h"

#include "re2/sparse_set.h"

namespace re2 {

static const bool ExtraDebug = false;

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);

 private:

  struct Thread {

    union {

      int ref;

      Thread* next;  // when on free list

    };

    const char** capture;

  };

  // State for explicit stack in AddToThreadq.

  struct AddState {

    int id;     // Inst to process

    Thread* t;  // if not null, set t0 = t before processing id

  };

  // 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 Thread* Incref(Thread* t);

  inline void Decref(Thread* t);

  // Follows all empty arrows from id0 and enqueues all the states reached.

  // Enqueues only the ByteRange instructions that match byte c.

  // context is used (with p) for evaluating empty-width specials.

  // p is the current input position, and t0 is the current thread.

  void AddToThreadq(Threadq* q, int id0, int c, const StringPiece& context,

                    const char* p, Thread* t0);

  // Run runq on byte c, appending new states to nextq.

  // Updates matched_ and match_ as new, better matches are found.

  // context is used (with p) for evaluating empty-width specials.

  // p is the position of byte c in the input string for AddToThreadq;

  // p-1 will be used when processing Match instructions.

  // Frees all the threads on runq.

  // If there is a shortcut to the end, returns that shortcut.

  int Step(Threadq* runq, Threadq* nextq, int c, const StringPiece& context,

           const char* p);

  // Returns text version of capture information, for debugging.

  std::string FormatCapture(const char** capture);

  void CopyCapture(const char** dst, const char** src) {

    memmove(dst, src, ncapture_*sizeof src[0]);

  }

  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 (for FormatSubmatch)

  const char* etext_;         // end of text (for endmatch_)

  Threadq q0_, q1_;           // pre-allocated for Search.

  PODArray<AddState> stack_;  // pre-allocated for AddToThreadq

  std::deque<Thread> arena_;  // thread arena

  Thread* freelist_;          // thread freelist

  const char** match_;        // best match so far

  bool matched_;              // any match so far?

  NFA(const NFA&) = delete;

  NFA& operator=(const NFA&) = delete;

};

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());

  // See NFA::AddToThreadq() for why this is so.

  int nstack = 2*prog_->inst_count(kInstCapture) +

               prog_->inst_count(kInstEmptyWidth) +

               prog_->inst_count(kInstNop) + 1;  // + 1 for start inst

  stack_ = PODArray<AddState>(nstack);

  freelist_ = NULL;

  match_ = NULL;

  matched_ = false;

}

NFA::~NFA() {

  delete[] match_;

  for (const Thread& t : arena_)

    delete[] t.capture;

}

NFA::Thread* NFA::AllocThread() {

  Thread* t = freelist_;

  if (t != NULL) {

    freelist_ = t->next;

    t->ref = 1;

    // We don't need to touch t->capture because

    // the caller will immediately overwrite it.

    return t;

  }

  arena_.emplace_back();

  t = &arena_.back();

  t->ref = 1;

  t->capture = new const char*[ncapture_];

  return t;

}

NFA::Thread* NFA::Incref(Thread* t) {

  DCHECK(t != NULL);

  t->ref++;

  return t;

}

void NFA::Decref(Thread* t) {

  DCHECK(t != NULL);

  t->ref--;

  if (t->ref > 0)

    return;

  DCHECK_EQ(t->ref, 0);

  t->next = freelist_;

  freelist_ = t;

}

// Follows all empty arrows from id0 and enqueues all the states reached.

// Enqueues only the ByteRange instructions that match byte c.

// context is used (with p) for evaluating empty-width specials.

// p is the current input position, and t0 is the current thread.

void NFA::AddToThreadq(Threadq* q, int id0, int c, const StringPiece& context,

                       const char* p, Thread* t0) {

  if (id0 == 0)

    return;

  // Use stack_ to hold our stack of instructions yet to process.

  // It was preallocated as follows:

  //   two entries per Capture;

  //   one entry per EmptyWidth; and

  //   one entry per Nop.

  // This reflects the maximum number of stack pushes that each can

  // perform. (Each instruction can be processed at most once.)

  AddState* stk = stack_.data();

  int nstk = 0;

  stk[nstk++] = {id0, NULL};

  while (nstk > 0) {

    DCHECK_LE(nstk, stack_.size());

    AddState a = stk[--nstk];

  Loop:

    if (a.t != NULL) {

      // t0 was a thread that we allocated and copied in order to

      // record the capture, so we must now decref it.

      Decref(t0);

      t0 = a.t;

    }

    int id = a.id;

    if (id == 0)

      continue;

    if (q->has_index(id)) {

      if (ExtraDebug)

        fprintf(stderr, "  [%d%s]\n", id, FormatCapture(t0->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->get_existing(id);

    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 = Incref(t0);

      *tp = t;

      DCHECK(!ip->last());

      a = {id+1, NULL};

      goto Loop;

    case kInstNop:

      if (!ip->last())

        stk[nstk++] = {id+1, NULL};

      // Continue on.

      a = {ip->out(), NULL};

      goto Loop;

    case kInstCapture:

      if (!ip->last())

        stk[nstk++] = {id+1, NULL};

      if ((j=ip->cap()) < ncapture_) {

        // Push a dummy whose only job is to restore t0

        // once we finish exploring this possibility.

        stk[nstk++] = {0, t0};

        // Record capture.

        t = AllocThread();

        CopyCapture(t->capture, t0->capture);

        t->capture[j] = p;

        t0 = t;

      }

      a = {ip->out(), NULL};

      goto Loop;

    case kInstByteRange:

      if (!ip->Matches(c))

        goto Next;

      // Save state; will pick up at next byte.

      t = Incref(t0);

      *tp = t;

      if (ExtraDebug)

        fprintf(stderr, " + %d%s\n", id, FormatCapture(t0->capture).c_str());

      if (ip->hint() == 0)

        break;

      a = {id+ip->hint(), NULL};

      goto Loop;

    case kInstMatch:

      // Save state; will pick up at next byte.

      t = Incref(t0);

      *tp = t;

      if (ExtraDebug)

        fprintf(stderr, " ! %d%s\n", id, FormatCapture(t0->capture).c_str());

    Next:

      if (ip->last())

        break;

      a = {id+1, NULL};

      goto Loop;

    case kInstEmptyWidth:

      if (!ip->last())

        stk[nstk++] = {id+1, NULL};

      // Continue on if we have all the right flag bits.

      if (ip->empty() & ~Prog::EmptyFlags(context, p))

        break;

      a = {ip->out(), NULL};

      goto Loop;

    }

  }

}

// Run runq on byte c, appending new states to nextq.

// Updates matched_ and match_ as new, better matches are found.

// context is used (with p) for evaluating empty-width specials.

// p is the position of byte c in the input string for AddToThreadq;

// p-1 will be used when processing Match instructions.

// 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, const StringPiece& context,

              const char* p) {

  nextq->clear();

  for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) {

    Thread* t = i->value();

    if (t == NULL)

      continue;

    if (longest_) {

      // Can skip any threads started after our current best match.

      if (matched_ && match_[0] < t->capture[0]) {

        Decref(t);

        continue;

      }

    }

    int id = i->index();

    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:

        AddToThreadq(nextq, ip->out(), c, context, p, t);

        break;

      case kInstAltMatch:

        if (i != runq->begin())

          break;

        // The match is ours if we want it.

        if (ip->greedy(prog_) || longest_) {

          CopyCapture(match_, t->capture);

          matched_ = true;

          Decref(t);

          for (++i; i != runq->end(); ++i) {

            if (i->value() != NULL)

              Decref(i->value());

          }

          runq->clear();

          if (ip->greedy(prog_))

            return ip->out1();

          return ip->out();

        }

        break;

      case kInstMatch: {

        // Avoid invoking undefined behavior (arithmetic on a null pointer)

        // by storing p instead of p-1. (What would the latter even mean?!)

        // This complements the special case in NFA::Search().

        if (p == NULL) {

          CopyCapture(match_, t->capture);

          match_[1] = p;

          matched_ = true;

          break;

        }

        if (endmatch_ && p-1 != etext_)

          break;

        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] && p-1 > match_[1])) {

            CopyCapture(match_, t->capture);

            match_[1] = p-1;

            matched_ = true;

          }

        } else {

          // Leftmost-biased mode: this match is by definition

          // better than what we've already found (see next line).

          CopyCapture(match_, t->capture);

          match_[1] = p-1;

          matched_ = true;

          // 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.

          Decref(t);

          for (++i; i != runq->end(); ++i) {

            if (i->value() != NULL)

              Decref(i->value());

          }

          runq->clear();

          return 0;

        }

        break;

      }

    }

    Decref(t);

  }

  runq->clear();

  return 0;

}

std::string NFA::FormatCapture(const char** capture) {

  std::string s;

  for (int i = 0; i < ncapture_; i+=2) {

    if (capture[i] == NULL)

      s += "(?,?)";

    else if (capture[i+1] == NULL)

      s += StringPrintf("(%td,?)",

                        capture[i] - btext_);

    else

      s += StringPrintf("(%td,%td)",

                        capture[i] - btext_,

                        capture[i+1] - btext_);

  }

  return s;

}

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.data() == NULL)

    context = text;

  // Sanity check: make sure that text lies within context.

  if (BeginPtr(text) < BeginPtr(context) || EndPtr(text) > EndPtr(context)) {

    LOG(DFATAL) << "context does not contain text";

    return false;

  }

  if (prog_->anchor_start() && BeginPtr(context) != BeginPtr(text))

    return false;

  if (prog_->anchor_end() && EndPtr(context) != EndPtr(text))

    return false;

  anchored |= prog_->anchor_start();

  if (prog_->anchor_end()) {

    longest = true;

    endmatch_ = true;

  }

  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_];

  memset(match_, 0, ncapture_*sizeof match_[0]);

  matched_ = false;

  // For debugging prints.

  btext_ = context.data();

  // For convenience.

  etext_ = text.data() + text.size();

  if (ExtraDebug)

    fprintf(stderr, "NFA::Search %s (context: %s) anchored=%d longest=%d\n",

            std::string(text).c_str(), std::string(context).c_str(), anchored, longest);

  // Set up search.

  Threadq* runq = &q0_;

  Threadq* nextq = &q1_;

  runq->clear();

  nextq->clear();

  // Loop over the text, stepping the machine.

  for (const char* p = text.data();; p++) {

    if (ExtraDebug) {

      int c = 0;

      if (p == btext_)

        c = '^';

      else if (p > etext_)

        c = '$';

      else if (p < etext_)

        c = p[0] & 0xFF;

      fprintf(stderr, "%c:", c);

      for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) {

        Thread* t = i->value();

        if (t == NULL)

          continue;

        fprintf(stderr, " %d%s", i->index(), FormatCapture(t->capture).c_str());

      }

      fprintf(stderr, "\n");

    }

    // This is a no-op the first time around the loop because runq is empty.

    int id = Step(runq, nextq, p < etext_ ? p[0] & 0xFF : -1, context, p);

    DCHECK_EQ(runq->size(), 0);

    using std::swap;

    swap(nextq, runq);

    nextq->clear();

    if (id != 0) {

      // We're done: full match ahead.

      p = etext_;

      for (;;) {

        Prog::Inst* ip = prog_->inst(id);

        switch (ip->opcode()) {

          default:

            LOG(DFATAL) << "Unexpected opcode in short circuit: " << ip->opcode();

            break;

          case kInstCapture:

            if (ip->cap() < ncapture_)

              match_[ip->cap()] = p;

            id = ip->out();

            continue;

          case kInstNop:

            id = ip->out();

            continue;

          case kInstMatch:

            match_[1] = p;

            matched_ = true;

            break;

        }

        break;

      }

      break;

    }

    if (p > etext_)

      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.data())) {

      // Try to use prefix accel (e.g. memchr) to skip ahead.

      // The search must be unanchored and there must be zero

      // possible matches already.

      if (!anchored && runq->size() == 0 &&

          p < etext_ && prog_->can_prefix_accel()) {

        p = reinterpret_cast<const char*>(prog_->PrefixAccel(p, etext_ - p));

        if (p == NULL)

          p = etext_;

      }

      Thread* t = AllocThread();

      CopyCapture(t->capture, match_);

      t->capture[0] = p;

      AddToThreadq(runq, start_, p < etext_ ? p[0] & 0xFF : -1, context, p,

                   t);

      Decref(t);

    }

    // If all the threads have died, stop early.

    if (runq->size() == 0) {

      if (ExtraDebug)

        fprintf(stderr, "dead\n");

      break;

    }

    // Avoid invoking undefined behavior (arithmetic on a null pointer)

    // by simply not continuing the loop.

    // This complements the special case in NFA::Step().

    if (p == NULL) {

      (void) Step(runq, nextq, -1, context, p);

      DCHECK_EQ(runq->size(), 0);

      using std::swap;

      swap(nextq, runq);

      nextq->clear();

      break;

    }

  }

  for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) {

    if (i->value() != NULL)

      Decref(i->value());

  }

  if (matched_) {

    for (int i = 0; i < nsubmatch; i++)

      submatch[i] =

          StringPiece(match_[2 * i],

                      static_cast<size_t>(match_[2 * i + 1] - match_[2 * i]));

    if (ExtraDebug)

      fprintf(stderr, "match (%td,%td)\n",

              match_[0] - btext_,

              match_[1] - btext_);

    return true;

  }

  return false;

}

bool

Prog::SearchNFA(const StringPiece& text, const StringPiece& context,

                Anchor anchor, MatchKind kind,

                StringPiece* match, int nmatch) {

  if (ExtraDebug)

    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 && EndPtr(match[0]) != EndPtr(text))

    return false;

  return true;

}

// For each instruction i in the program reachable from the start, compute the

// number of instructions reachable from i by following only empty transitions

// and record that count as fanout[i].

//

// fanout holds the results and is also the work queue for the outer iteration.

// reachable holds the reached nodes for the inner iteration.

void Prog::Fanout(SparseArray<int>* fanout) {

  DCHECK_EQ(fanout->max_size(), size());

  SparseSet reachable(size());

  fanout->clear();

  fanout->set_new(start(), 0);

  for (SparseArray<int>::iterator i = fanout->begin(); i != fanout->end(); ++i) {

    int* count = &i->value();

    reachable.clear();

    reachable.insert(i->index());

    for (SparseSet::iterator j = reachable.begin(); j != reachable.end(); ++j) {

      int id = *j;

      Prog::Inst* ip = inst(id);

      switch (ip->opcode()) {

        default:

          LOG(DFATAL) << "unhandled " << ip->opcode() << " in Prog::Fanout()";

          break;

        case kInstByteRange:

          if (!ip->last())

            reachable.insert(id+1);

          (*count)++;

          if (!fanout->has_index(ip->out())) {

            fanout->set_new(ip->out(), 0);

          }

          break;

        case kInstAltMatch:

          DCHECK(!ip->last());

          reachable.insert(id+1);

          break;

        case kInstCapture:

        case kInstEmptyWidth:

        case kInstNop:

          if (!ip->last())

            reachable.insert(id+1);

          reachable.insert(ip->out());

          break;

        case kInstMatch:

          if (!ip->last())

            reachable.insert(id+1);

          break;

        case kInstFail:

          break;

      }

    }

  }

}

}  // namespace re2