content: // Copyright 2010 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  // Original Go source here:
  // http://code.google.com/p/go/source/browse/src/pkg/regexp/syntax/prog.go
  
  package com.github.aaronshan.functions.regexp.re2j;
  
  import io.airlift.slice.SliceOutput;
  import io.airlift.slice.Slices;
  
  import java.util.ArrayList;
  import java.util.List;
  
  import static com.github.aaronshan.functions.regexp.re2j.Inst.Op.BYTE;
  import static com.github.aaronshan.functions.regexp.re2j.Inst.Op.MATCH;
  
  /**
   * A Prog is a compiled regular expression program.
   */
  class Prog {
  
      private final List<com.github.aaronshan.functions.regexp.re2j.Inst> inst = new ArrayList<com.github.aaronshan.functions.regexp.re2j.Inst>();
      int start; // index of start instruction
      int startUnanchored; // index of unanchored start instruction
      int numCap = 2; // number of CAPTURE insts in re
      // 2 => implicit ( and ) for whole match $0
  
      // Constructs an empty program.
      Prog() {
      }
  
      // Returns the instruction at the specified pc.
      // Precondition: pc > 0 && pc < numInst().
      com.github.aaronshan.functions.regexp.re2j.Inst getInst(int pc) {
          return inst.get(pc);
      }
  
      com.github.aaronshan.functions.regexp.re2j.Inst[] getInst() {
          return inst.toArray(new com.github.aaronshan.functions.regexp.re2j.Inst[inst.size()]);
      }
  
      // Returns the number of instructions in this program.
      int numInst() {
          return inst.size();
      }
  
      // Adds a new instruction to this program, with operator |op| and |pc| equal
      // to |numInst()|.
      void addInst(com.github.aaronshan.functions.regexp.re2j.Inst.Op op) {
          inst.add(new com.github.aaronshan.functions.regexp.re2j.Inst(op));
      }
  
      // skipNop() follows any no-op or capturing instructions and returns the
      // resulting instruction.
      com.github.aaronshan.functions.regexp.re2j.Inst skipNop(int pc) {
          com.github.aaronshan.functions.regexp.re2j.Inst i = inst.get(pc);
          while (i.op == com.github.aaronshan.functions.regexp.re2j.Inst.Op.NOP || i.op == com.github.aaronshan.functions.regexp.re2j.Inst.Op.CAPTURE) {
              i = inst.get(pc);
              pc = i.out;
          }
          return i;
      }
  
      // prefix() returns a pair of a literal slice that all matches for the
      // regexp must start with, and a boolean which is true if the prefix is the
      // entire match.  The slice is returned by appending to |prefix|.
      boolean prefix(SliceOutput prefix) {
          com.github.aaronshan.functions.regexp.re2j.Inst i = skipNop(start);
  
          // Avoid allocation of buffer if prefix is empty.
          if (i.op() != BYTE || i.byteRanges.length != 1) {
              return i.op == MATCH;  // (append "" to prefix)
          }
  
          int length = 0;
          while (i.op() == BYTE && i.byteRanges.length == 1) {
              i = skipNop(i.out);
              length++;
          }
  
          byte[] bytes = new byte[length];
          length = 0;
          i = skipNop(start);
          while (i.op() == BYTE && i.byteRanges.length == 1) {
              bytes[length] = i.byteRanges[0];
              i = skipNop(i.out);
              length++;
          }
  
          // Have prefix; gather characters.
          prefix.appendBytes(Slices.wrappedBuffer(bytes));
  
          return i.op == MATCH;
      }
  
      // startCond() returns the leading empty-width conditions that must be true
      // in any match.  It returns -1 (all bits set) if no matches are possible.
      int startCond() {
          int flag = 0;  // bitmask of EMPTY_* flags
          int pc = start;
          loop:
          for (; ; ) {
              com.github.aaronshan.functions.regexp.re2j.Inst i = inst.get(pc);
              switch (i.op) {
                  case EMPTY_WIDTH:
                      flag |= i.arg;
                      break;
                  case FAIL:
                      return -1;
                  case CAPTURE:
                  case NOP:
                      break;  // skip
                  default:
                      break loop;
              }
              pc = i.out;
          }
          return flag;
      }
  
      // --- Patch list ---
  
      // A patchlist is a list of instruction pointers that need to be filled in
      // (patched).  Because the pointers haven't been filled in yet, we can reuse
      // their storage to hold the list.  It's kind of sleazy, but works well in
      // practice.  See http://swtch.com/~rsc/regexp/regexp1.html for inspiration.
  
      // These aren't really pointers: they're integers, so we can reinterpret them
      // this way without using package unsafe.  A value l denotes p.inst[l>>1].out
      // (l&1==0) or .arg (l&1==1).  l == 0 denotes the empty list, okay because we
      // start every program with a fail instruction, so we'll never want to point
      // at its output link.
  
      int next(int l) {
          com.github.aaronshan.functions.regexp.re2j.Inst i = inst.get(l >> 1);
          if ((l & 1) == 0) {
              return i.out;
          }
          return i.arg;
      }
  
      void patch(int l, int val) {
          while (l != 0) {
              com.github.aaronshan.functions.regexp.re2j.Inst i = inst.get(l >> 1);
              if ((l & 1) == 0) {
                  l = i.out;
                  i.out = val;
              } else {
                  l = i.arg;
                  i.arg = val;
              }
          }
      }
  
      int append(int l1, int l2) {
          if (l1 == 0) {
              return l2;
          }
          if (l2 == 0) {
              return l1;
          }
          int last = l1;
          for (; ; ) {
              int next = next(last);
              if (next == 0) {
                  break;
              }
              last = next;
          }
          com.github.aaronshan.functions.regexp.re2j.Inst i = inst.get(last >> 1);
          if ((last & 1) == 0) {
              i.out = l2;
          } else {
              i.arg = l2;
          }
          return l1;
      }
  
      // ---
  
      @Override
      public String toString() {
          StringBuilder out = new StringBuilder();
          for (int pc = 0; pc < inst.size(); ++pc) {
              int len = out.length();
              out.append(pc);
              if (pc == start) {
                  out.append('*');
              }
              if (pc == startUnanchored) {
                  out.append("@");
              }
              // Use spaces not tabs since they're not always preserved in
              // Google Java source, such as our tests.
              out.append("        ".substring(out.length() - len)).
                      append(inst.get(pc)).append('\n');
          }
          return out.toString();
      }
  }
  