lucene/analysis/common/src/test/org/apache/lucene/analysis/pattern/TestPatternReplaceCharFilter.java

/*
 * 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.
 */
package org.apache.lucene.analysis.pattern;

import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.BaseTokenStreamTestCase;
import org.apache.lucene.analysis.CharFilter;
import org.apache.lucene.analysis.MockTokenizer;
import org.apache.lucene.analysis.TokenStream;
import org.apache.lucene.analysis.Tokenizer;
import org.apache.lucene.util.TestUtil;
import org.junit.Ignore;

/** Tests {@link PatternReplaceCharFilter} */
public class TestPatternReplaceCharFilter extends BaseTokenStreamTestCase {
  public void testFailingDot() throws IOException {
    checkOutput("A. .B.", "\\.[\\s]*", ".", "A..B.", "A..B.");
  }

  public void testLongerReplacement() throws IOException {
    checkOutput("XXabcZZabcYY", "abc", "abcde", "XXabcdeZZabcdeYY", "XXabcccZZabcccYY");
    checkOutput("XXabcabcYY", "abc", "abcde", "XXabcdeabcdeYY", "XXabcccabcccYY");
    checkOutput("abcabcYY", "abc", "abcde", "abcdeabcdeYY", "abcccabcccYY");
    checkOutput(
        "YY",
        "^",
        "abcde",
        "abcdeYY",
        // Should be: "-----YY" but we're enforcing non-negative offsets.
        "YYYYYYY");
    checkOutput("YY", "$", "abcde", "YYabcde", "YYYYYYY");
    checkOutput("XYZ", ".", "abc", "abcabcabc", "XXXYYYZZZ");
    checkOutput("XYZ", ".", "$0abc", "XabcYabcZabc", "XXXXYYYYZZZZ");
  }

  public void testShorterReplacement() throws IOException {
    checkOutput("XXabcZZabcYY", "abc", "xy", "XXxyZZxyYY", "XXabZZabYY");
    checkOutput("XXabcabcYY", "abc", "xy", "XXxyxyYY", "XXababYY");
    checkOutput("abcabcYY", "abc", "xy", "xyxyYY", "ababYY");
    checkOutput("abcabcYY", "abc", "", "YY", "YY");
    checkOutput("YYabcabc", "abc", "", "YY", "YY");
  }

  private void checkOutput(
      String input,
      String pattern,
      String replacement,
      String expectedOutput,
      String expectedIndexMatchedOutput)
      throws IOException {
    CharFilter cs =
        new PatternReplaceCharFilter(pattern(pattern), replacement, new StringReader(input));

    StringBuilder output = new StringBuilder();
    for (int chr = cs.read(); chr > 0; chr = cs.read()) {
      output.append((char) chr);
    }

    StringBuilder indexMatched = new StringBuilder();
    for (int i = 0; i < output.length(); i++) {
      indexMatched.append((cs.correctOffset(i) < 0 ? "-" : input.charAt(cs.correctOffset(i))));
    }

    boolean outputGood = expectedOutput.equals(output.toString());
    boolean indexMatchedGood = expectedIndexMatchedOutput.equals(indexMatched.toString());

    if (!outputGood || !indexMatchedGood || false) {
      System.out.println("Pattern : " + pattern);
      System.out.println("Replac. : " + replacement);
      System.out.println("Input   : " + input);
      System.out.println("Output  : " + output);
      System.out.println("Expected: " + expectedOutput);
      System.out.println("Output/i: " + indexMatched);
      System.out.println("Expected: " + expectedIndexMatchedOutput);
      System.out.println();
    }

    assertTrue("Output doesn't match.", outputGood);
    assertTrue("Index-matched output doesn't match.", indexMatchedGood);
  }

  //           1111
  // 01234567890123
  // this is test.
  public void testNothingChange() throws IOException {
    final String BLOCK = "this is test.";
    CharFilter cs =
        new PatternReplaceCharFilter(
            pattern("(aa)\\s+(bb)\\s+(cc)"), "$1$2$3", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts,
        new String[] {"this", "is", "test."},
        new int[] {0, 5, 8},
        new int[] {4, 7, 13},
        BLOCK.length());
  }

  // 012345678
  // aa bb cc
  public void testReplaceByEmpty() throws IOException {
    final String BLOCK = "aa bb cc";
    CharFilter cs =
        new PatternReplaceCharFilter(pattern("(aa)\\s+(bb)\\s+(cc)"), "", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(ts, new String[] {});
  }

  // 012345678
  // aa bb cc
  // aa#bb#cc
  public void test1block1matchSameLength() throws IOException {
    final String BLOCK = "aa bb cc";
    CharFilter cs =
        new PatternReplaceCharFilter(
            pattern("(aa)\\s+(bb)\\s+(cc)"), "$1#$2#$3", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts, new String[] {"aa#bb#cc"}, new int[] {0}, new int[] {8}, BLOCK.length());
  }

  //           11111
  // 012345678901234
  // aa bb cc dd
  // aa##bb###cc dd
  public void test1block1matchLonger() throws IOException {
    final String BLOCK = "aa bb cc dd";
    CharFilter cs =
        new PatternReplaceCharFilter(
            pattern("(aa)\\s+(bb)\\s+(cc)"), "$1##$2###$3", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts,
        new String[] {"aa##bb###cc", "dd"},
        new int[] {0, 9},
        new int[] {8, 11},
        BLOCK.length());
  }

  // 01234567
  //  a  a
  //  aa  aa
  public void test1block2matchLonger() throws IOException {
    final String BLOCK = " a  a";
    CharFilter cs = new PatternReplaceCharFilter(pattern("a"), "aa", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts, new String[] {"aa", "aa"}, new int[] {1, 4}, new int[] {2, 5}, BLOCK.length());
  }

  //           11111
  // 012345678901234
  // aa  bb   cc dd
  // aa#bb dd
  public void test1block1matchShorter() throws IOException {
    final String BLOCK = "aa  bb   cc dd";
    CharFilter cs =
        new PatternReplaceCharFilter(
            pattern("(aa)\\s+(bb)\\s+(cc)"), "$1#$2", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts, new String[] {"aa#bb", "dd"}, new int[] {0, 12}, new int[] {11, 14}, BLOCK.length());
  }

  //           111111111122222222223333
  // 0123456789012345678901234567890123
  //   aa bb cc --- aa bb aa   bb   cc
  //   aa  bb  cc --- aa bb aa  bb  cc
  public void test1blockMultiMatches() throws IOException {
    final String BLOCK = "  aa bb cc --- aa bb aa   bb   cc";
    CharFilter cs =
        new PatternReplaceCharFilter(
            pattern("(aa)\\s+(bb)\\s+(cc)"), "$1  $2  $3", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts,
        new String[] {"aa", "bb", "cc", "---", "aa", "bb", "aa", "bb", "cc"},
        new int[] {2, 6, 9, 11, 15, 18, 21, 25, 29},
        new int[] {4, 8, 10, 14, 17, 20, 23, 27, 33},
        BLOCK.length());
  }

  //           11111111112222222222333333333
  // 012345678901234567890123456789012345678
  //   aa bb cc --- aa bb aa. bb aa   bb cc
  //   aa##bb cc --- aa##bb aa. bb aa##bb cc

  //   aa bb cc --- aa bbbaa. bb aa   b cc

  public void test2blocksMultiMatches() throws IOException {
    final String BLOCK = "  aa bb cc --- aa bb aa. bb aa   bb cc";

    CharFilter cs =
        new PatternReplaceCharFilter(pattern("(aa)\\s+(bb)"), "$1##$2", new StringReader(BLOCK));
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts,
        new String[] {"aa##bb", "cc", "---", "aa##bb", "aa.", "bb", "aa##bb", "cc"},
        new int[] {2, 8, 11, 15, 21, 25, 28, 36},
        new int[] {7, 10, 14, 20, 24, 27, 35, 38},
        BLOCK.length());
  }

  //           11111111112222222222333333333
  // 012345678901234567890123456789012345678
  //  a bb - ccc . --- bb a . ccc ccc bb
  //  aa b - c . --- b aa . c c b
  public void testChain() throws IOException {
    final String BLOCK = " a bb - ccc . --- bb a . ccc ccc bb";
    CharFilter cs = new PatternReplaceCharFilter(pattern("a"), "aa", new StringReader(BLOCK));
    cs = new PatternReplaceCharFilter(pattern("bb"), "b", cs);
    cs = new PatternReplaceCharFilter(pattern("ccc"), "c", cs);
    TokenStream ts = whitespaceMockTokenizer(cs);
    assertTokenStreamContents(
        ts,
        new String[] {"aa", "b", "-", "c", ".", "---", "b", "aa", ".", "c", "c", "b"},
        new int[] {1, 3, 6, 8, 12, 14, 18, 21, 23, 25, 29, 33},
        new int[] {2, 5, 7, 11, 13, 17, 20, 22, 24, 28, 32, 35},
        BLOCK.length());
  }

  private Pattern pattern(String p) {
    return Pattern.compile(p);
  }

  /**
   * A demonstration of how backtracking regular expressions can lead to relatively easy DoS
   * attacks.
   *
   * @see <a
   *     href="http://swtch.com/~rsc/regexp/regexp1.html">"http://swtch.com/~rsc/regexp/regexp1.html"</a>
   */
  @Ignore
  public void testNastyPattern() throws Exception {
    Pattern p = Pattern.compile("(c.+)*xy");
    String input =
        "[;<!--aecbbaa--><    febcfdc fbb = \"fbeeebff\" fc = dd   >\\';<eefceceaa e= babae\" eacbaff =\"fcfaccacd\" = bcced>>><  bccaafe edb = ecfccdff\"   <?</script><    edbd ebbcd=\"faacfcc\" aeca= bedbc ceeaac =adeafde aadccdaf = \"afcc ffda=aafbe &#x16921ed5\"1843785582']";
    for (int i = 0; i < input.length(); i++) {
      Matcher matcher = p.matcher(input.substring(0, i));
      long t = System.currentTimeMillis();
      if (matcher.find()) {
        System.out.println(matcher.group());
      }
      System.out.println(i + " > " + (System.currentTimeMillis() - t) / 1000.0);
    }
  }

  /** blast some random strings through the analyzer */
  public void testRandomStrings() throws Exception {
    int numPatterns = 5;
    Random random = new Random(random().nextLong());
    for (int i = 0; i < numPatterns; i++) {
      final Pattern p = TestUtil.randomPattern(random());

      final String replacement = TestUtil.randomSimpleString(random);
      Analyzer a =
          new Analyzer() {
            @Override
            protected TokenStreamComponents createComponents(String fieldName) {
              Tokenizer tokenizer = new MockTokenizer(MockTokenizer.WHITESPACE, false);
              return new TokenStreamComponents(tokenizer, tokenizer);
            }

            @Override
            protected Reader initReader(String fieldName, Reader reader) {
              return new PatternReplaceCharFilter(p, replacement, reader);
            }
          };

      /* max input length. don't make it longer -- exponential processing
       * time for certain patterns. */
      final int maxInputLength = 30;
      /* ASCII only input?: */
      final boolean asciiOnly = true;
      checkRandomData(random, a, 50 * RANDOM_MULTIPLIER, maxInputLength, asciiOnly);
      a.close();
    }
  }
}