content: package org.apache.lucene.analysis.synonym;
  
  /**
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to You under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  import java.io.IOException;
  
  import org.apache.lucene.analysis.TokenFilter;
  import org.apache.lucene.analysis.TokenStream;
  import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
  import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
  import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
  import org.apache.lucene.analysis.tokenattributes.TypeAttribute;
  import org.apache.lucene.store.ByteArrayDataInput;
  import org.apache.lucene.util.ArrayUtil;
  import org.apache.lucene.util.AttributeSource;
  import org.apache.lucene.util.BytesRef;
  import org.apache.lucene.util.CharsRef;
  import org.apache.lucene.util.RamUsageEstimator;
  import org.apache.lucene.util.UnicodeUtil;
  import org.apache.lucene.util.fst.FST;
  
  /**
   * Matches single or multi word synonyms in a token stream.
   * This token stream cannot properly handle position
   * increments != 1, ie, you should place this filter before
   * filtering out stop words.
   * 
   * <p>Note that with the current implementation, parsing is
   * greedy, so whenever multiple parses would apply, the rule
   * starting the earliest and parsing the most tokens wins.
   * For example if you have these rules:
   *      
   * <pre>
   *   a -> x
   *   a b -> y
   *   b c d -> z
   * </pre>
   *
   * Then input <code>a b c d e</code> parses to <code>y b c
   * d</code>, ie the 2nd rule "wins" because it started
   * earliest and matched the most input tokens of other rules
   * starting at that point.</p>
   *
   * <p>A future improvement to this filter could allow
   * non-greedy parsing, such that the 3rd rule would win, and
   * also separately allow multiple parses, such that all 3
   * rules would match, perhaps even on a rule by rule
   * basis.</p>
   *
   * <p><b>NOTE</b>: when a match occurs, the output tokens
   * associated with the matching rule are "stacked" on top of
   * the input stream (if the rule had
   * <code>keepOrig=true</code>) and also on top of aother
   * matched rule's output tokens.  This is not a correct
   * solution, as really the output should be an abitrary
   * graph/lattice.  For example, with the above match, you
   * would expect an exact <code>PhraseQuery</code> <code>"y b
   * c"</code> to match the parsed tokens, but it will fail to
   * do so.  This limitations is necessary because Lucene's
   * TokenStream (and index) cannot yet represent an arbitrary
   * graph.</p>
   *
   * <p><b>NOTE</b>: If multiple incoming tokens arrive on the
   * same position, only the first token at that position is
   * used for parsing.  Subsequent tokens simply pass through
   * and are not parsed.  A future improvement would be to
   * allow these tokens to also be matched.</p>
   */ 
  
  // TODO: maybe we should resolve token -> wordID then run
  // FST on wordIDs, for better perf?
  
  // TODO: a more efficient approach would be Aho/Corasick's
  // algorithm
  // http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
  // It improves over the current approach here
  // because it does not fully re-start matching at every
  // token.  For exampl,e if one pattern is "a b c x"
  // and another is "b c d" and the input is "a b c d", on
  // trying to parse "a b c x" but failing when you got to x,
  // rather than starting over again your really should
  // immediately recognize that "b c d" matches at the next
  // input.  I suspect this won't matter that much in
  // practice, but it's possible on some set of synonyms it
  // will.  We'd have to modify Aho/Corasick to enforce our
  // conflict resolving (eg greedy matching) because that algo
  // finds all matches.
  
  public final class SynonymFilter extends TokenFilter {
  
    public static final String TYPE_SYNONYM = "SYNONYM";
  
    private final SynonymMap synonyms;
  
    private final boolean ignoreCase;
    private final int rollBufferSize;
  
    private int captureCount;
  
    private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
    private final PositionIncrementAttribute posIncrAtt = addAttribute(PositionIncrementAttribute.class);
    private final TypeAttribute typeAtt = addAttribute(TypeAttribute.class);
    private final OffsetAttribute offsetAtt = addAttribute(OffsetAttribute.class);
  
    // How many future input tokens have already been matched
    // to a synonym; because the matching is "greedy" we don't
    // try to do any more matching for such tokens:
    private int inputSkipCount;
  
    // Hold all buffered (read ahead) stacked input tokens for
    // a future position.  When multiple tokens are at the
    // same position, we only store (and match against) the
    // term for the first token at the position, but capture
    // state for (and enumerate) all other tokens at this
    // position:
    private static class PendingInput {
      final CharsRef term = new CharsRef();
      AttributeSource.State state;
      boolean keepOrig;
      boolean matched;
      boolean consumed = true;
      int startOffset;
      int endOffset;
      
      public void reset() {
        state = null;
        consumed = true;
        keepOrig = false;
        matched = false;
      }
    };
  
    // Rolling buffer, holding pending input tokens we had to
    // clone because we needed to look ahead, indexed by
    // position:
    private final PendingInput[] futureInputs;
  
    // Holds pending output synonyms for one future position:
    private static class PendingOutputs {
      CharsRef[] outputs;
      int upto;
      int count;
      int posIncr = 1;
  
      public PendingOutputs() {
        outputs = new CharsRef[1];
      }
  
      public void reset() {
        upto = count = 0;
        posIncr = 1;
      }
  
      public CharsRef pullNext() {
        assert upto < count;
        final CharsRef result = outputs[upto++];
        posIncr = 0;
        if (upto == count) {
          reset();
        }
        return result;
      }
  
      public void add(char[] output, int offset, int len) {
        if (count == outputs.length) {
          final CharsRef[] next = new CharsRef[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
          System.arraycopy(outputs, 0, next, 0, count);
          outputs = next;
        }
        if (outputs[count] == null) {
          outputs[count] = new CharsRef();
        }
        outputs[count].copy(output, offset, len);
        count++;
      }
    };
  
    private final ByteArrayDataInput bytesReader = new ByteArrayDataInput();
  
    // Rolling buffer, holding stack of pending synonym
    // outputs, indexed by position:
    private final PendingOutputs[] futureOutputs;
  
    // Where (in rolling buffers) to write next input saved state:
    private int nextWrite;
  
    // Where (in rolling buffers) to read next input saved state:
    private int nextRead;
  
    // True once we've read last token
    private boolean finished;
  
    private final FST.Arc<BytesRef> scratchArc;
  
    private final FST<BytesRef> fst;
  
    private final BytesRef scratchBytes = new BytesRef();
    private final CharsRef scratchChars = new CharsRef();
  
    /**
     * @param input input tokenstream
     * @param synonyms synonym map
     * @param ignoreCase case-folds input for matching with {@link Character#toLowerCase(int)}.
     *                   Note, if you set this to true, its your responsibility to lowercase
     *                   the input entries when you create the {@link SynonymMap}
     */
    public SynonymFilter(TokenStream input, SynonymMap synonyms, boolean ignoreCase) {
      super(input);
      this.synonyms = synonyms;
      this.ignoreCase = ignoreCase;
      this.fst = synonyms.fst;
  
      if (fst == null) {
        throw new IllegalArgumentException("fst must be non-null");
      }
  
      // Must be 1+ so that when roll buffer is at full
      // lookahead we can distinguish this full buffer from
      // the empty buffer:
      rollBufferSize = 1+synonyms.maxHorizontalContext;
  
      futureInputs = new PendingInput[rollBufferSize];
      futureOutputs = new PendingOutputs[rollBufferSize];
      for(int pos=0;pos<rollBufferSize;pos++) {
        futureInputs[pos] = new PendingInput();
        futureOutputs[pos] = new PendingOutputs();
      }
  
      //System.out.println("FSTFilt maxH=" + synonyms.maxHorizontalContext);
  
      scratchArc = new FST.Arc<BytesRef>();
    }
  
    private void capture() {
      captureCount++;
      //System.out.println("  capture slot=" + nextWrite);
      final PendingInput input = futureInputs[nextWrite];
  
      input.state = captureState();
      input.consumed = false;
      input.term.copy(termAtt.buffer(), 0, termAtt.length());
  
      nextWrite = rollIncr(nextWrite);
  
      // Buffer head should never catch up to tail:
      assert nextWrite != nextRead;
    }
  
    /*
     This is the core of this TokenFilter: it locates the
     synonym matches and buffers up the results into
     futureInputs/Outputs.
  
     NOTE: this calls input.incrementToken and does not
     capture the state if no further tokens were checked.  So
     caller must then forward state to our caller, or capture:
    */
  
    private void parse() throws IOException {
      //System.out.println("\nS: parse");
  
      assert inputSkipCount == 0;
  
      int curNextRead = nextRead;
  
      // Holds the longest match we've seen so far:
      BytesRef matchOutput = null;
      int matchInputLength = 0;
  
      BytesRef pendingOutput = fst.outputs.getNoOutput();
      fst.getFirstArc(scratchArc);
  
      assert scratchArc.output == fst.outputs.getNoOutput();
  
      int tokenCount = 0;
  
      byToken:
      while(true) {
        
        // Pull next token's chars:
        final char[] buffer;
        final int bufferLen;
        //System.out.println("  cycle nextRead=" + curNextRead + " nextWrite=" + nextWrite);
  
        if (curNextRead == nextWrite) {
  
          // We used up our lookahead buffer of input tokens
          // -- pull next real input token:
  
          if (finished) {
            break;
          } else  {
            //System.out.println("  input.incrToken");
            assert futureInputs[nextWrite].consumed;
            // Not correct: a syn match whose output is longer
            // than its input can set future inputs keepOrig
            // to true:
            //assert !futureInputs[nextWrite].keepOrig;
            if (input.incrementToken()) {
              buffer = termAtt.buffer();
              bufferLen = termAtt.length();
              final PendingInput input = futureInputs[nextWrite];
              input.startOffset = offsetAtt.startOffset();
              input.endOffset = offsetAtt.endOffset();
              //System.out.println("  new token=" + new String(buffer, 0, bufferLen));
              if (nextRead != nextWrite) {
                capture();
              } else {
                input.consumed = false;
              }
  
            } else {
              // No more input tokens
              //System.out.println("      set end");
              finished = true;
              break;
            }
          }
        } else {
          // Still in our lookahead
          buffer = futureInputs[curNextRead].term.chars;
          bufferLen = futureInputs[curNextRead].term.length;
          //System.out.println("  old token=" + new String(buffer, 0, bufferLen));
        }
  
        tokenCount++;
  
        // Run each char in this token through the FST:
        int bufUpto = 0;
        while(bufUpto < bufferLen) {
          final int codePoint = Character.codePointAt(buffer, bufUpto, bufferLen);
          if (fst.findTargetArc(ignoreCase ? Character.toLowerCase(codePoint) : codePoint, scratchArc, scratchArc) == null) {
            //System.out.println("    stop");
            break byToken;
          }
  
          // Accum the output
          pendingOutput = fst.outputs.add(pendingOutput, scratchArc.output);
          //System.out.println("    char=" + buffer[bufUpto] + " output=" + pendingOutput + " arc.output=" + scratchArc.output);
          bufUpto += Character.charCount(codePoint);
        }
  
        // OK, entire token matched; now see if this is a final
        // state:
        if (scratchArc.isFinal()) {
          matchOutput = fst.outputs.add(pendingOutput, scratchArc.nextFinalOutput);
          matchInputLength = tokenCount;
          //System.out.println("  found matchLength=" + matchInputLength + " output=" + matchOutput);
        }
  
        // See if the FST wants to continue matching (ie, needs to
        // see the next input token):
        if (fst.findTargetArc(SynonymMap.WORD_SEPARATOR, scratchArc, scratchArc) == null) {
          // No further rules can match here; we're done
          // searching for matching rules starting at the
          // current input position.
          break;
        } else {
          // More matching is possible -- accum the output (if
          // any) of the WORD_SEP arc:
          pendingOutput = fst.outputs.add(pendingOutput, scratchArc.output);
          if (nextRead == nextWrite) {
            capture();
          }
        }
  
        curNextRead = rollIncr(curNextRead);
      }
  
      if (nextRead == nextWrite && !finished) {
        //System.out.println("  skip write slot=" + nextWrite);
        nextWrite = rollIncr(nextWrite);
      }
  
      if (matchOutput != null) {
        //System.out.println("  add matchLength=" + matchInputLength + " output=" + matchOutput);
        inputSkipCount = matchInputLength;
        addOutput(matchOutput, matchInputLength);
      } else if (nextRead != nextWrite) {
        // Even though we had no match here, we set to 1
        // because we need to skip current input token before
        // trying to match again:
        inputSkipCount = 1;
      } else {
        assert finished;
      }
  
      //System.out.println("  parse done inputSkipCount=" + inputSkipCount + " nextRead=" + nextRead + " nextWrite=" + nextWrite);
    }
  
    // Interleaves all output tokens onto the futureOutputs:
    private void addOutput(BytesRef bytes, int matchInputLength) {
      bytesReader.reset(bytes.bytes, bytes.offset, bytes.length);
  
      final int code = bytesReader.readVInt();
      final boolean keepOrig = (code & 0x1) == 0;
      final int count = code >>> 1;
      //System.out.println("  addOutput count=" + count + " keepOrig=" + keepOrig);
      for(int outputIDX=0;outputIDX<count;outputIDX++) {
        synonyms.words.get(bytesReader.readVInt(),
                           scratchBytes);
        //System.out.println("    outIDX=" + outputIDX + " bytes=" + scratchBytes.length);
        UnicodeUtil.UTF8toUTF16(scratchBytes, scratchChars);
        int lastStart = scratchChars.offset;
        final int chEnd = lastStart + scratchChars.length;
        int outputUpto = nextRead;
        for(int chIDX=lastStart;chIDX<=chEnd;chIDX++) {
          if (chIDX == chEnd || scratchChars.chars[chIDX] == SynonymMap.WORD_SEPARATOR) {
            final int outputLen = chIDX - lastStart;
            // Caller is not allowed to have empty string in
            // the output:
            assert outputLen > 0: "output contains empty string: " + scratchChars;
            futureOutputs[outputUpto].add(scratchChars.chars, lastStart, outputLen);
            //System.out.println("      " + new String(scratchChars.chars, lastStart, outputLen) + " outputUpto=" + outputUpto);
            lastStart = 1+chIDX;
            //System.out.println("  slot=" + outputUpto + " keepOrig=" + keepOrig);
            outputUpto = rollIncr(outputUpto);
            assert futureOutputs[outputUpto].posIncr == 1: "outputUpto=" + outputUpto + " vs nextWrite=" + nextWrite;
          }
        }
      }
  
      int upto = nextRead;
      for(int idx=0;idx<matchInputLength;idx++) {
        futureInputs[upto].keepOrig |= keepOrig;
        futureInputs[upto].matched = true;
        upto = rollIncr(upto);
      }
    }
  
    // ++ mod rollBufferSize
    private int rollIncr(int count) {
      count++;
      if (count == rollBufferSize) {
        return 0;
      } else {
        return count;
      }
    }
  
    // for testing
    int getCaptureCount() {
      return captureCount;
    }
  
    @Override
    public boolean incrementToken() throws IOException {
  
      //System.out.println("\nS: incrToken inputSkipCount=" + inputSkipCount + " nextRead=" + nextRead + " nextWrite=" + nextWrite);
  
      while(true) {
  
        // First play back any buffered future inputs/outputs
        // w/o running parsing again:
        while (inputSkipCount != 0) {
          
          // At each position, we first output the original
          // token
  
          // TODO: maybe just a PendingState class, holding
          // both input & outputs?
          final PendingInput input = futureInputs[nextRead];
          final PendingOutputs outputs = futureOutputs[nextRead];
          
          //System.out.println("  cycle nextRead=" + nextRead + " nextWrite=" + nextWrite + " inputSkipCount="+ inputSkipCount + " input.keepOrig=" + input.keepOrig + " input.consumed=" + input.consumed + " input.state=" + input.state);
  
          if (!input.consumed && (input.keepOrig || !input.matched)) {
            if (input.state != null) {
              // Return a previously saved token (because we
              // had to lookahead):
              restoreState(input.state);
            } else {
              // Pass-through case: return token we just pulled
              // but didn't capture:
              assert inputSkipCount == 1: "inputSkipCount=" + inputSkipCount + " nextRead=" + nextRead;
            }
            input.reset();
            if (outputs.count > 0) {
              outputs.posIncr = 0;
            } else {
              nextRead = rollIncr(nextRead);
              inputSkipCount--;
            }
            //System.out.println("  return token=" + termAtt.toString());
            return true;
          } else if (outputs.upto < outputs.count) {
            // Still have pending outputs to replay at this
            // position
            input.reset();
            final int posIncr = outputs.posIncr;
            final CharsRef output = outputs.pullNext();
            clearAttributes();
            termAtt.copyBuffer(output.chars, output.offset, output.length);
            typeAtt.setType(TYPE_SYNONYM);
            offsetAtt.setOffset(input.startOffset, input.endOffset);
            posIncrAtt.setPositionIncrement(posIncr);
            if (outputs.count == 0) {
              // Done with the buffered input and all outputs at
              // this position
              nextRead = rollIncr(nextRead);
              inputSkipCount--;
            }
            //System.out.println("  return token=" + termAtt.toString());
            return true;
          } else {
            // Done with the buffered input and all outputs at
            // this position
            input.reset();
            nextRead = rollIncr(nextRead);
            inputSkipCount--;
          }
        }
  
        if (finished && nextRead == nextWrite) {
          // End case: if any output syns went beyond end of
          // input stream, enumerate them now:
          final PendingOutputs outputs = futureOutputs[nextRead];
          if (outputs.upto < outputs.count) {
            final int posIncr = outputs.posIncr;
            final CharsRef output = outputs.pullNext();
            futureInputs[nextRead].reset();
            if (outputs.count == 0) {
              nextWrite = nextRead = rollIncr(nextRead);
            }
            clearAttributes();
            termAtt.copyBuffer(output.chars, output.offset, output.length);
            typeAtt.setType(TYPE_SYNONYM);
            //System.out.println("  set posIncr=" + outputs.posIncr + " outputs=" + outputs);
            posIncrAtt.setPositionIncrement(posIncr);
            //System.out.println("  return token=" + termAtt.toString());
            return true;
          } else {
            return false;
          }
        }
  
        // Find new synonym matches:
        parse();
      }
    }
  
    @Override
    public void reset() throws IOException {
      super.reset();
      captureCount = 0;
      finished = false;
  
      // In normal usage these resets would not be needed,
      // since they reset-as-they-are-consumed, but the app
      // may not consume all input tokens in which case we
      // have leftover state here:
      for (PendingInput input : futureInputs) {
        input.reset();
      }
      for (PendingOutputs output : futureOutputs) {
        output.reset();
      }
    }
  }
  