text: // 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.
  //
  // Prog::SearchOnePass is an efficient implementation of
  // regular expression search with submatch tracking for
  // what I call "one-pass regular expressions".  (An alternate
  // name might be "backtracking-free regular expressions".)
  //
  // One-pass regular expressions have the property that
  // at each input byte during an anchored match, there may be
  // multiple alternatives but only one can proceed for any
  // given input byte.
  //
  // For example, the regexp /x*yx*/ is one-pass: you read
  // x's until a y, then you read the y, then you keep reading x's.
  // At no point do you have to guess what to do or back up
  // and try a different guess.
  //
  // On the other hand, /x*x/ is not one-pass: when you're
  // looking at an input "x", it's not clear whether you should
  // use it to extend the x* or as the final x.
  //
  // More examples: /([^ ]*) (.*)/ is one-pass; /(.*) (.*)/ is not.
  // /(\d+)-(\d+)/ is one-pass; /(\d+).(\d+)/ is not.
  //
  // A simple intuition for identifying one-pass regular expressions
  // is that it's always immediately obvious when a repetition ends.
  // It must also be immediately obvious which branch of an | to take:
  //
  // /x(y|z)/ is one-pass, but /(xy|xz)/ is not.
  //
  // The NFA-based search in nfa.cc does some bookkeeping to
  // avoid the need for backtracking and its associated exponential blowup.
  // But if we have a one-pass regular expression, there is no
  // possibility of backtracking, so there is no need for the
  // extra bookkeeping.  Hence, this code.
  //
  // On a one-pass regular expression, the NFA code in nfa.cc
  // runs at about 1/20 of the backtracking-based PCRE speed.
  // In contrast, the code in this file runs at about the same
  // speed as PCRE.
  //
  // One-pass regular expressions get used a lot when RE is
  // used for parsing simple strings, so it pays off to
  // notice them and handle them efficiently.
  //
  // See also Anne Brüggemann-Klein and Derick Wood,
  // "One-unambiguous regular languages", Information and Computation 142(2).
  
  #include <string.h>
  #include <map>
  #include "util/util.h"
  #include "util/sparse_set.h"
  #include "re2/prog.h"
  #include "re2/stringpiece.h"
  
  namespace re2 {
  
  static const int Debug = 0;
  
  // The key insight behind this implementation is that the
  // non-determinism in an NFA for a one-pass regular expression
  // is contained.  To explain what that means, first a
  // refresher about what regular expression programs look like
  // and how the usual NFA execution runs.
  //
  // In a regular expression program, only the kInstByteRange
  // instruction processes an input byte c and moves on to the
  // next byte in the string (it does so if c is in the given range).
  // The kInstByteRange instructions correspond to literal characters
  // and character classes in the regular expression.
  //
  // The kInstAlt instructions are used as wiring to connect the
  // kInstByteRange instructions together in interesting ways when
  // implementing | + and *.
  // The kInstAlt instruction forks execution, like a goto that
  // jumps to ip->out() and ip->out1() in parallel.  Each of the
  // resulting computation paths is called a thread.
  //
  // The other instructions -- kInstEmptyWidth, kInstMatch, kInstCapture --
  // are interesting in their own right but like kInstAlt they don't
  // advance the input pointer.  Only kInstByteRange does.
  //
  // The automaton execution in nfa.cc runs all the possible
  // threads of execution in lock-step over the input.  To process
  // a particular byte, each thread gets run until it either dies
  // or finds a kInstByteRange instruction matching the byte.
  // If the latter happens, the thread stops just past the
  // kInstByteRange instruction (at ip->out()) and waits for
  // the other threads to finish processing the input byte.
  // Then, once all the threads have processed that input byte,
  // the whole process repeats.  The kInstAlt state instruction
  // might create new threads during input processing, but no
  // matter what, all the threads stop after a kInstByteRange
  // and wait for the other threads to "catch up".
  // Running in lock step like this ensures that the NFA reads
  // the input string only once.
  //
  // Each thread maintains its own set of capture registers
  // (the string positions at which it executed the kInstCapture
  // instructions corresponding to capturing parentheses in the
  // regular expression).  Repeated copying of the capture registers
  // is the main performance bottleneck in the NFA implementation.
  //
  // A regular expression program is "one-pass" if, no matter what
  // the input string, there is only one thread that makes it
  // past a kInstByteRange instruction at each input byte.  This means
  // that there is in some sense only one active thread throughout
  // the execution.  Other threads might be created during the
  // processing of an input byte, but they are ephemeral: only one
  // thread is left to start processing the next input byte.
  // This is what I meant above when I said the non-determinism
  // was "contained".
  //
  // To execute a one-pass regular expression program, we can build
  // a DFA (no non-determinism) that has at most as many states as
  // the NFA (compare this to the possibly exponential number of states
  // in the general case).  Each state records, for each possible
  // input byte, the next state along with the conditions required
  // before entering that state -- empty-width flags that must be true
  // and capture operations that must be performed.  It also records
  // whether a set of conditions required to finish a match at that
  // point in the input rather than process the next byte.
  
  // A state in the one-pass NFA - just an array of actions indexed
  // by the bytemap_[] of the next input byte.  (The bytemap
  // maps next input bytes into equivalence classes, to reduce
  // the memory footprint.)
  struct OneState {
    uint32 matchcond;   // conditions to match right now.
    uint32 action[1];
  };
  
  // The uint32 conditions in the action are a combination of
  // condition and capture bits and the next state.  The bottom 16 bits
  // are the condition and capture bits, and the top 16 are the index of
  // the next state.
  //
  // Bits 0-5 are the empty-width flags from prog.h.
  // Bit 6 is kMatchWins, which means the match takes
  // priority over moving to next in a first-match search.
  // The remaining bits mark capture registers that should
  // be set to the current input position.  The capture bits
  // start at index 2, since the search loop can take care of
  // cap[0], cap[1] (the overall match position).
  // That means we can handle up to 5 capturing parens: $1 through $4, plus $0.
  // No input position can satisfy both kEmptyWordBoundary
  // and kEmptyNonWordBoundary, so we can use that as a sentinel
  // instead of needing an extra bit.
  
  static const int    kIndexShift    = 16;  // number of bits below index
  static const int    kEmptyShift   = 6;  // number of empty flags in prog.h
  static const int    kRealCapShift = kEmptyShift + 1;
  static const int    kRealMaxCap   = (kIndexShift - kRealCapShift) / 2 * 2;
  
  // Parameters used to skip over cap[0], cap[1].
  static const int    kCapShift     = kRealCapShift - 2;
  static const int    kMaxCap       = kRealMaxCap + 2;
  
  static const uint32 kMatchWins    = 1 << kEmptyShift;
  static const uint32 kCapMask      = ((1 << kRealMaxCap) - 1) << kRealCapShift;
  
  static const uint32 kImpossible   = kEmptyWordBoundary | kEmptyNonWordBoundary;
  
  // Check, at compile time, that prog.h agrees with math above.
  // This function is never called.
  void OnePass_Checks() {
    COMPILE_ASSERT((1<<kEmptyShift)-1 == kEmptyAllFlags,
                   kEmptyShift_disagrees_with_kEmptyAllFlags);
    // kMaxCap counts pointers, kMaxOnePassCapture counts pairs.
    COMPILE_ASSERT(kMaxCap == Prog::kMaxOnePassCapture*2,
                   kMaxCap_disagrees_with_kMaxOnePassCapture);
  }
  
  template<typename StrPiece>
  static bool Satisfy(uint32 cond, const StrPiece& context, typename StrPiece::ptr_rd_type p) {
    uint32 satisfied = Prog::EmptyFlags(context, p);
    if (cond & kEmptyAllFlags & ~satisfied)
      return false;
    return true;
  }
  
  // Apply the capture bits in cond, saving p to the appropriate
  // locations in cap[].
  template<typename ptr_rd_type, typename ptr_type>
  static void ApplyCaptures(uint32 cond, ptr_rd_type p,
                            ptr_type* cap, int ncap) {
    for (int i = 2; i < ncap; i++)
      if (cond & (1 << kCapShift << i))
        cap[i] = p;
  }
  
  // Compute a node pointer.
  // Basically (OneState*)(nodes + statesize*nodeindex)
  // but the version with the C++ casts overflows 80 characters (and is ugly).
  static inline OneState* IndexToNode(volatile uint8* nodes, int statesize,
                                      int nodeindex) {
    return reinterpret_cast<OneState*>(
      const_cast<uint8*>(nodes + statesize*nodeindex));
  }
  
  template<typename StrPiece>
  bool Prog::SearchOnePass(const StrPiece& text,
                           const StrPiece& const_context,
                           Anchor anchor, MatchKind kind,
                           StrPiece* match, int nmatch) {
    typedef typename StrPiece::ptr_type ptr_type;
    typedef typename StrPiece::ptr_rd_type ptr_rd_type;
  
    if (anchor != kAnchored && kind != kFullMatch) {
      LOG(DFATAL) << "Cannot use SearchOnePass for unanchored matches.";
      return false;
    }
  
    // Make sure we have at least cap[1],
    // because we use it to tell if we matched.
    int ncap = 2*nmatch;
    if (ncap < 2)
      ncap = 2;
  
    ptr_type cap[kMaxCap];
    for (int i = 0; i < ncap; i++)
      cap[i] = StrPiece::null_ptr();
  
    ptr_type matchcap[kMaxCap];
    for (int i = 0; i < ncap; i++)
      matchcap[i] = StrPiece::null_ptr();
  
    StrPiece context = const_context;
    if (context.begin() == StrPiece::null_ptr())
      context = text;
    if (anchor_start() && context.begin() != text.begin())
      return false;
    if (anchor_end() && context.end() != text.end())
      return false;
    if (anchor_end())
      kind = kFullMatch;
  
    // State and act are marked volatile to
    // keep the compiler from re-ordering the
    // memory accesses walking over the NFA.
    // This is worth about 5%.
    volatile OneState* state = onepass_start_;
    volatile uint8* nodes = onepass_nodes_;
    volatile uint32 statesize = onepass_statesize_;
    uint8* bytemap = bytemap_;
    ptr_type bp = text.begin();
    ptr_type ep = text.end();
    ptr_rd_type p = text.begin_reading();
    bool matched = false;
    matchcap[0] = bp;
    cap[0] = bp;
    uint32 nextmatchcond = state->matchcond;
    for (; p < ep; p++) {
      int c = bytemap[*p & 0xFF];
      uint32 matchcond = nextmatchcond;
      uint32 cond = state->action[c];
  
      // Determine whether we can reach act->next.
      // If so, advance state and nextmatchcond.
      if ((cond & kEmptyAllFlags) == 0 || Satisfy(cond, context, p)) {
        uint32 nextindex = cond >> kIndexShift;
        state = IndexToNode(nodes, statesize, nextindex);
        nextmatchcond = state->matchcond;
      } else {
        state = NULL;
        nextmatchcond = kImpossible;
      }
  
      // This code section is carefully tuned.
      // The goto sequence is about 10% faster than the
      // obvious rewrite as a large if statement in the
      // ASCIIMatchRE2 and DotMatchRE2 benchmarks.
  
      // Saving the match capture registers is expensive.
      // Is this intermediate match worth thinking about?
  
      // Not if we want a full match.
      if (kind == kFullMatch)
        goto skipmatch;
  
      // Not if it's impossible.
      if (matchcond == kImpossible)
        goto skipmatch;
  
      // Not if the possible match is beaten by the certain
      // match at the next byte.  When this test is useless
      // (e.g., HTTPPartialMatchRE2) it slows the loop by
      // about 10%, but when it avoids work (e.g., DotMatchRE2),
      // it cuts the loop execution by about 45%.
      if ((cond & kMatchWins) == 0 && (nextmatchcond & kEmptyAllFlags) == 0 &&
          text.can_discard(p-bp) )
        goto skipmatch;
  
      // Finally, the match conditions must be satisfied.
      if ((matchcond & kEmptyAllFlags) == 0 || Satisfy(matchcond, context, p)) {
        for (int i = 2; i < 2*nmatch; i++)
          matchcap[i] = cap[i];
        if (nmatch > 1 && (matchcond & kCapMask))
          ApplyCaptures(matchcond, p, matchcap, ncap);
        matchcap[1] = p;
        matched = true;
        // If we're in longest match mode, we have to keep
        // going and see if we find a longer match.
        // In first match mode, we can stop if the match
        // takes priority over the next state for this input byte.
        // That bit is per-input byte and thus in cond, not matchcond.
        if (kind == kFirstMatch && (cond & kMatchWins))
          goto done;
      }
  
    skipmatch:
      if (state == NULL)
        goto done;
      if ((cond & kCapMask) && nmatch > 1)
        ApplyCaptures(cond, p, cap, ncap);
  
      // Occasionally compute the minimum match position in
      // and let e.g. a FILE* know that it can drop
      // buffers from earlier portions.
      if ( text.can_discard(p-bp) ) {
        ptr_type min_start;
        ptr_type min_end;
        ptr_type min_cap;
        // Optimization above might not set matched if there is a certain
        // match at the next byte.
        //bool match_or_nextmatch = matched |
       //   ((cond & kMatchWins) == 0 && (nextmatchcond & kEmptyAllFlags) == 0);
        min_start = cap[0];
        if( cap[1] >= cap[0] ) min_end = cap[1];
        else min_end = p;
        min_cap = p;
        for (int k = 2; k < 2*nmatch; k+=2 ) {
          if ( cap[k] < min_cap ) min_cap = cap[k];
        }
        // Let e.g. a FILE* know of the minimum starting position.
        text.discard(matched, min_start, min_end, min_cap);
      }
  
    }
  
    // Look for match at end of input.
    {
      uint32 matchcond = state->matchcond;
      if (matchcond != kImpossible &&
          ((matchcond & kEmptyAllFlags) == 0 || Satisfy(matchcond, context, p))) {
        if (nmatch > 1 && (matchcond & kCapMask))
          ApplyCaptures(matchcond, p, cap, ncap);
        for (int i = 2; i < ncap; i++)
          matchcap[i] = cap[i];
        matchcap[1] = p;
        matched = true;
      }
    }
  
  done:
    if (!matched)
      return false;
    for (int i = 0; i < nmatch; i++)
      match[i].set_ptr_end(matchcap[2*i], matchcap[2*i+1]);
    return true;
  }
  
  template
  bool Prog::SearchOnePass<StringPiece>(
                           const StringPiece& text,
                           const StringPiece& const_context,
                           Anchor anchor, MatchKind kind,
                           StringPiece* match, int nmatch);
  
  template
  bool Prog::SearchOnePass<FilePiece>(
                           const FilePiece& text,
                           const FilePiece& const_context,
                           Anchor anchor, MatchKind kind,
                           FilePiece* match, int nmatch);
  
  // Analysis to determine whether a given regexp program is one-pass.
  
  // If ip is not on workq, adds ip to work queue and returns true.
  // If ip is already on work queue, does nothing and returns false.
  // If ip is NULL, does nothing and returns true (pretends to add it).
  typedef SparseSet Instq;
  static bool AddQ(Instq *q, int id) {
    if (id == 0)
      return true;
    if (q->contains(id))
      return false;
    q->insert(id);
    return true;
  }
  
  struct InstCond {
    int id;
    uint32 cond;
  };
  
  // Returns whether this is a one-pass program; that is,
  // returns whether it is safe to use SearchOnePass on this program.
  // These conditions must be true for any instruction ip:
  //
  //   (1) for any other Inst nip, there is at most one input-free
  //       path from ip to nip.
  //   (2) there is at most one kInstByte instruction reachable from
  //       ip that matches any particular byte c.
  //   (3) there is at most one input-free path from ip to a kInstMatch
  //       instruction.
  //
  // This is actually just a conservative approximation: it might
  // return false when the answer is true, when kInstEmptyWidth
  // instructions are involved.
  // Constructs and saves corresponding one-pass NFA on success.
  bool Prog::IsOnePass() {
    if (did_onepass_)
      return onepass_start_ != NULL;
    did_onepass_ = true;
  
    if (start() == 0)  // no match
      return false;
  
    // Steal memory for the one-pass NFA from the overall DFA budget.
    // Willing to use at most 1/4 of the DFA budget (heuristic).
    // Limit max node count to 65000 as a conservative estimate to
    // avoid overflowing 16-bit node index in encoding.
    int maxnodes = 2 + byte_inst_count_;
    int statesize = sizeof(OneState) + (bytemap_range_-1)*sizeof(uint32);
    if (maxnodes >= 65000 || dfa_mem_ / 4 / statesize < maxnodes)
      return false;
  
    // Flood the graph starting at the start state, and check
    // that in each reachable state, each possible byte leads
    // to a unique next state.
    int size = this->size();
    InstCond *stack = new InstCond[size];
  
    int* nodebyid = new int[size];  // indexed by ip
    memset(nodebyid, 0xFF, size*sizeof nodebyid[0]);
  
    uint8* nodes = new uint8[maxnodes*statesize];
    uint8* nodep = nodes;
  
    Instq tovisit(size), workq(size);
    AddQ(&tovisit, start());
    nodebyid[start()] = 0;
    nodep += statesize;
    int nalloc = 1;
    for (Instq::iterator it = tovisit.begin(); it != tovisit.end(); ++it) {
      int id = *it;
      int nodeindex = nodebyid[id];
      OneState* node = IndexToNode(nodes, statesize, nodeindex);
  
      // Flood graph using manual stack, filling in actions as found.
      // Default is none.
      for (int b = 0; b < bytemap_range_; b++)
        node->action[b] = kImpossible;
      node->matchcond = kImpossible;
  
      workq.clear();
      bool matched = false;
      int nstack = 0;
      stack[nstack].id = id;
      stack[nstack++].cond = 0;
      while (nstack > 0) {
        int id = stack[--nstack].id;
        Prog::Inst* ip = inst(id);
        uint32 cond = stack[nstack].cond;
        switch (ip->opcode()) {
          case kInstAltMatch:
            // TODO(rsc): Ignoring kInstAltMatch optimization.
            // Should implement it in this engine, but it's subtle.
            // Fall through.
          case kInstAlt:
            // If already on work queue, (1) is violated: bail out.
            if (!AddQ(&workq, ip->out()) || !AddQ(&workq, ip->out1()))
              goto fail;
            stack[nstack].id = ip->out1();
            stack[nstack++].cond = cond;
            stack[nstack].id = ip->out();
            stack[nstack++].cond = cond;
            break;
  
          case kInstByteRange: {
            int nextindex = nodebyid[ip->out()];
            if (nextindex == -1) {
              if (nalloc >= maxnodes) {
                if (Debug)
                  LOG(ERROR)
                    << StringPrintf("Not OnePass: hit node limit %d > %d",
                                    nalloc, maxnodes);
                goto fail;
              }
              nextindex = nalloc;
              nodep += statesize;
              nodebyid[ip->out()] = nextindex;
              nalloc++;
              AddQ(&tovisit, ip->out());
            }
            if (matched)
              cond |= kMatchWins;
            for (int c = ip->lo(); c <= ip->hi(); c++) {
              int b = bytemap_[c];
              c = unbytemap_[b];  // last c in byte class
              uint32 act = node->action[b];
              uint32 newact = (nextindex << kIndexShift) | cond;
              if ((act & kImpossible) == kImpossible) {
                node->action[b] = newact;
              } else if (act != newact) {
                if (Debug) {
                  LOG(ERROR)
                    << StringPrintf("Not OnePass: conflict on byte "
                                    "%#x at state %d",
                                    c, *it);
                }
                goto fail;
              }
            }
            if (ip->foldcase()) {
              Rune lo = max<Rune>(ip->lo(), 'a') + 'A' - 'a';
              Rune hi = min<Rune>(ip->hi(), 'z') + 'A' - 'a';
              for (int c = lo; c <= hi; c++) {
                int b = bytemap_[c];
                c = unbytemap_[b];  // last c in class
                uint32 act = node->action[b];
                uint32 newact = (nextindex << kIndexShift) | cond;
                if ((act & kImpossible) == kImpossible) {
                  node->action[b] = newact;
                } else if (act != newact) {
                  if (Debug) {
                    LOG(ERROR)
                      << StringPrintf("Not OnePass: conflict on byte "
                                      "%#x at state %d",
                                      c, *it);
                  }
                  goto fail;
                }
              }
            }
            break;
          }
  
          case kInstCapture:
            if (ip->cap() < kMaxCap)
              cond |= (1 << kCapShift) << ip->cap();
            goto QueueEmpty;
  
          case kInstEmptyWidth:
            cond |= ip->empty();
            goto QueueEmpty;
  
          case kInstNop:
          QueueEmpty:
            // kInstCapture and kInstNop always proceed to ip->out().
            // kInstEmptyWidth only sometimes proceeds to ip->out(),
            // but as a conservative approximation we assume it always does.
            // We could be a little more precise by looking at what c
            // is, but that seems like overkill.
  
            // If already on work queue, (1) is violated: bail out.
            if (!AddQ(&workq, ip->out())) {
              if (Debug) {
                LOG(ERROR) << StringPrintf("Not OnePass: multiple paths"
                                           " %d -> %d\n",
                                           *it, ip->out());
              }
              goto fail;
            }
            stack[nstack].id = ip->out();
            stack[nstack++].cond = cond;
            break;
  
          case kInstMatch:
            if (matched) {
              // (3) is violated
              if (Debug) {
                LOG(ERROR) << StringPrintf("Not OnePass: multiple matches"
                                           " from %d\n", *it);
              }
              goto fail;
            }
            matched = true;
            node->matchcond = cond;
            break;
  
          case kInstFail:
            break;
        }
      }
    }
  
    if (Debug) {  // For debugging, dump one-pass NFA to LOG(ERROR).
      string dump = "prog dump:\n" + Dump() + "node dump\n";
      map<int, int> idmap;
      for (int i = 0; i < size; i++)
        if (nodebyid[i] != -1)
          idmap[nodebyid[i]] = i;
  
      StringAppendF(&dump, "byte ranges:\n");
      int i = 0;
      for (int b = 0; b < bytemap_range_; b++) {
        int lo = i;
        while (bytemap_[i] == b)
          i++;
        StringAppendF(&dump, "\t%d: %#x-%#x\n", b, lo, i - 1);
      }
  
      for (Instq::iterator it = tovisit.begin(); it != tovisit.end(); ++it) {
        int id = *it;
        int nodeindex = nodebyid[id];
        if (nodeindex == -1)
        	continue;
        OneState* node = IndexToNode(nodes, statesize, nodeindex);
        string s;
        StringAppendF(&dump, "node %d id=%d: matchcond=%#x\n",
                      nodeindex, id, node->matchcond);
        for (int i = 0; i < bytemap_range_; i++) {
          if ((node->action[i] & kImpossible) == kImpossible)
            continue;
          StringAppendF(&dump, "  %d cond %#x -> %d id=%d\n",
                        i, node->action[i] & 0xFFFF,
                        node->action[i] >> kIndexShift,
                        idmap[node->action[i] >> kIndexShift]);
        }
      }
      LOG(ERROR) << dump;
    }
  
    // Overallocated earlier; cut down to actual size.
    nodep = new uint8[nalloc*statesize];
    memmove(nodep, nodes, nalloc*statesize);
    delete[] nodes;
    nodes = nodep;
  
    onepass_start_ = IndexToNode(nodes, statesize, nodebyid[start()]);
    onepass_nodes_ = nodes;
    onepass_statesize_ = statesize;
    dfa_mem_ -= nalloc*statesize;
  
    delete[] stack;
    delete[] nodebyid;
    return true;
  
  fail:
    delete[] stack;
    delete[] nodebyid;
    delete[] nodes;
    return false;
  }
  
  }  // namespace re2
  