SONAR-1091 Update library for detection of duplicates

4 files changed, 354 insertions, 0 deletions

diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockChunkerTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockChunkerTest.java
new file mode 100644
index 00000000000..548b8e0c436
--- /dev/null
+++ b/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockChunkerTest.java
@@ -0,0 +1,63 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.block;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertThat;
+
+import java.util.List;
+
+import org.junit.Test;
+import org.sonar.duplications.statement.Statement;
+
+public class BlockChunkerTest extends BlockChunkerTestCase {
+
+  @Override
+  protected BlockChunker createChunkerWithBlockSize(int blockSize) {
+    return new BlockChunker(blockSize);
+  }
+
+  /**
+   * Rolling hash must produce exactly the same values as without rolling behavior.
+   * Moreover those values must always be the same (without dependency on JDK).
+   */
+  @Test
+  public void shouldCalculateHashes() {
+    List<Statement> statements = createStatementsFromStrings("aaaaaa", "bbbbbb", "cccccc", "dddddd", "eeeeee");
+    BlockChunker blockChunker = createChunkerWithBlockSize(3);
+    List<Block> blocks = blockChunker.chunk("resource", statements);
+    assertThat(blocks.get(0).getBlockHash(), equalTo(hash("aaaaaa", "bbbbbb", "cccccc")));
+    assertThat(blocks.get(1).getBlockHash(), equalTo(hash("bbbbbb", "cccccc", "dddddd")));
+    assertThat(blocks.get(2).getBlockHash(), equalTo(hash("cccccc", "dddddd", "eeeeee")));
+    assertThat(blocks.get(0).getBlockHash().toString(), is("fffffeb6ae1af4c0"));
+    assertThat(blocks.get(1).getBlockHash().toString(), is("fffffebd8512d120"));
+    assertThat(blocks.get(2).getBlockHash().toString(), is("fffffec45c0aad80"));
+  }
+
+  private ByteArray hash(String... statements) {
+    long hash = 0;
+    for (String statement : statements) {
+      hash = hash * 31 + statement.hashCode();
+    }
+    return new ByteArray(hash);
+  }
+
+}
diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockChunkerTestCase.java b/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockChunkerTestCase.java
new file mode 100644
index 00000000000..90413bb2287
--- /dev/null
+++ b/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockChunkerTestCase.java
@@ -0,0 +1,145 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.block;
+
+import static org.hamcrest.Matchers.equalTo;
+import static org.hamcrest.Matchers.is;
+import static org.hamcrest.Matchers.not;
+import static org.hamcrest.Matchers.sameInstance;
+import static org.junit.Assert.assertThat;
+
+import java.util.Collections;
+import java.util.List;
+
+import org.junit.Test;
+import org.sonar.duplications.statement.Statement;
+
+import com.google.common.collect.Lists;
+
+/**
+ * Any implementation of {@link BlockChunker} should pass these test scenarios.
+ */
+public abstract class BlockChunkerTestCase {
+
+  /**
+   * Factory method.
+   */
+  protected abstract BlockChunker createChunkerWithBlockSize(int blockSize);
+
+  /**
+   * Given:
+   * <pre>
+   * String[][] data = {
+   *   {"a", "a"},
+   *   {"a", "a"},
+   *   {"a"},
+   *   {"a", "a"},
+   *   {"a", "a"}
+   * };
+   *
+   * Statements (where L - literal, C - comma): "LCL", "C", "LCL", "C", "L", "C", "LCL", "C", "LCL"
+   * Block size is 5.
+   * First block: "LCL", "C", "LCL", "C", "L"
+   * Last block: "L", "C", "LCL", "C", "LCL"
+   * </pre>
+   * Expected: different hashes for first and last blocks
+   */
+  @Test
+  public void testSameChars() {
+    List<Statement> statements = createStatementsFromStrings("LCL", "C", "LCL", "C", "L", "C", "LCL", "C", "LCL");
+    BlockChunker chunker = createChunkerWithBlockSize(5);
+    List<Block> blocks = chunker.chunk("resource", statements);
+    assertThat("first and last block should have different hashes", blocks.get(0).getBlockHash(), not(equalTo(blocks.get(blocks.size() - 1).getBlockHash())));
+  }
+
+  /**
+   * TODO Godin: should we allow empty statements in general?
+   */
+  @Test
+  public void testEmptyStatements() {
+    List<Statement> statements = createStatementsFromStrings("1", "", "1", "1", "");
+    BlockChunker chunker = createChunkerWithBlockSize(3);
+    List<Block> blocks = chunker.chunk("resource", statements);
+    assertThat("first and last block should have different hashes", blocks.get(0).getBlockHash(), not(equalTo(blocks.get(blocks.size() - 1).getBlockHash())));
+  }
+
+  /**
+   * Given: 5 statements, block size is 3
+   * Expected: 4 blocks with correct index and with line numbers
+   */
+  @Test
+  public void shouldBuildBlocksFromStatements() {
+    List<Statement> statements = createStatementsFromStrings("1", "2", "3", "4", "5", "6");
+    BlockChunker chunker = createChunkerWithBlockSize(3);
+    List<Block> blocks = chunker.chunk("resource", statements);
+    assertThat(blocks.size(), is(4));
+    assertThat(blocks.get(0).getIndexInFile(), is(0));
+    assertThat(blocks.get(0).getFirstLineNumber(), is(0));
+    assertThat(blocks.get(0).getLastLineNumber(), is(2));
+    assertThat(blocks.get(1).getIndexInFile(), is(1));
+    assertThat(blocks.get(1).getFirstLineNumber(), is(1));
+    assertThat(blocks.get(1).getLastLineNumber(), is(3));
+  }
+
+  @Test
+  public void testHashes() {
+    List<Statement> statements = createStatementsFromStrings("1", "2", "1", "2");
+    BlockChunker chunker = createChunkerWithBlockSize(2);
+    List<Block> blocks = chunker.chunk("resource", statements);
+    assertThat("blocks 0 and 2 should have same hash", blocks.get(0).getBlockHash(), equalTo(blocks.get(2).getBlockHash()));
+    assertThat("blocks 0 and 1 should have different hash", blocks.get(0).getBlockHash(), not(equalTo(blocks.get(1).getBlockHash())));
+  }
+
+  /**
+   * Given: 0 statements
+   * Expected: 0 blocks
+   */
+  @Test
+  public void shouldNotBuildBlocksWhenNoStatements() {
+    List<Statement> statements = Collections.emptyList();
+    BlockChunker blockChunker = createChunkerWithBlockSize(2);
+    List<Block> blocks = blockChunker.chunk("resource", statements);
+    assertThat(blocks, sameInstance(Collections.EMPTY_LIST));
+  }
+
+  /**
+   * Given: 1 statement, block size is 2
+   * Expected: 0 blocks
+   */
+  @Test
+  public void shouldNotBuildBlocksWhenNotEnoughStatements() {
+    List<Statement> statements = createStatementsFromStrings("statement");
+    BlockChunker blockChunker = createChunkerWithBlockSize(2);
+    List<Block> blocks = blockChunker.chunk("resource", statements);
+    assertThat(blocks, sameInstance(Collections.EMPTY_LIST));
+  }
+
+  /**
+   * Creates list of statements from Strings, each statement on a new line starting from 0.
+   */
+  protected static List<Statement> createStatementsFromStrings(String... values) {
+    List<Statement> result = Lists.newArrayList();
+    for (int i = 0; i < values.length; i++) {
+      result.add(new Statement(i, i, values[i]));
+    }
+    return result;
+  }
+
+}
diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockTest.java
new file mode 100644
index 00000000000..3aeba301d5a
--- /dev/null
+++ b/sonar-duplications/src/test/java/org/sonar/duplications/block/BlockTest.java
@@ -0,0 +1,80 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.block;
+
+import org.junit.Test;
+
+import static org.hamcrest.Matchers.*;
+import static org.junit.Assert.*;
+
+public class BlockTest {
+
+  @Test
+  public void fieldsTest() {
+    String fileName = "someFile";
+    int statementIndex = 4;
+    ByteArray hash = new ByteArray(12345);
+    Block tuple = new Block(fileName, hash, statementIndex, 0, 10);
+    assertThat(tuple.getResourceId(), equalTo(fileName));
+    assertThat(tuple.getIndexInFile(), equalTo(statementIndex));
+    assertEquals(tuple.getBlockHash(), hash);
+  }
+
+  @Test
+  public void tupleEqualsTest() {
+    Block tuple1 = new Block("somefile", new ByteArray(123), 1, 1, 10);
+    Block tuple2 = new Block("somefile", new ByteArray(123), 1, 1, 10);
+    Block tupleArr = new Block("somefile", new ByteArray(333), 1, 1, 10);
+    Block tupleIndex = new Block("somefile", new ByteArray(123), 2, 1, 10);
+    Block tupleName = new Block("other", new ByteArray(123), 1, 1, 10);
+
+    assertTrue(tuple1.equals(tuple2));
+    assertThat(tuple1.toString(), is(tuple2.toString()));
+
+    assertFalse(tuple1.equals(tupleArr));
+    assertThat(tuple1.toString(), not(equalTo(tupleArr.toString())));
+
+    assertFalse(tuple1.equals(tupleIndex));
+    assertThat(tuple1.toString(), not(equalTo(tupleIndex.toString())));
+
+    assertFalse(tuple1.equals(tupleName));
+    assertThat(tuple1.toString(), not(equalTo(tupleName.toString())));
+  }
+
+  @Test
+  public void hashCodeTest() {
+    String[] files = {"file1", "file2"};
+    int[] unitIndexes = {1, 2};
+    ByteArray[] arrays = {new ByteArray(123), new ByteArray(321)};
+
+    // fileName is in hashCode()
+    int defaultTupleHashCode = new Block(files[0], arrays[0], unitIndexes[0], 1, 10).hashCode();
+    int fileNameTupleHashCode = new Block(files[1], arrays[0], unitIndexes[0], 1, 10).hashCode();
+    assertThat(defaultTupleHashCode, not(equalTo(fileNameTupleHashCode)));
+
+    // statementIndex is in hashCode()
+    int indexTupleHashCode = new Block(files[0], arrays[0], unitIndexes[1], 1, 10).hashCode();
+    assertThat(defaultTupleHashCode, not(equalTo(indexTupleHashCode)));
+
+    // sequenceHash is in hashCode()
+    int sequenceHashTupleHashCode = new Block(files[0], arrays[1], unitIndexes[0], 1, 10).hashCode();
+    assertThat(defaultTupleHashCode, not(equalTo(sequenceHashTupleHashCode)));
+  }
+}
diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/block/ByteArrayTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/block/ByteArrayTest.java
new file mode 100644
index 00000000000..c237439f42e
--- /dev/null
+++ b/sonar-duplications/src/test/java/org/sonar/duplications/block/ByteArrayTest.java
@@ -0,0 +1,66 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.block;
+
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertThat;
+
+import org.junit.Test;
+
+public class ByteArrayTest {
+
+  @Test
+  public void shouldCreateFromInt() {
+    int value = 0x12FF8413;
+    ByteArray byteArray = new ByteArray(value);
+    assertThat(byteArray.toString(), is(Integer.toHexString(value)));
+  }
+
+  @Test
+  public void shouldCreateFromLong() {
+    long value = 0x12FF841344567899L;
+    ByteArray byteArray = new ByteArray(value);
+    assertThat(byteArray.toString(), is(Long.toHexString(value)));
+  }
+
+  @Test
+  public void shouldCreateFromHexString() {
+    String value = "12FF841344567899";
+    ByteArray byteArray = new ByteArray(value);
+    assertThat(byteArray.toString(), is(value.toLowerCase()));
+  }
+
+  @Test
+  public void shouldCreateFromIntArray() {
+    ByteArray byteArray = new ByteArray(new int[] { 0x04121986 });
+    assertThat(byteArray.toString(), is("04121986"));
+  }
+
+  @Test
+  public void shouldConvertToIntArray() {
+    // number of bytes is enough to create exactly one int (4 bytes)
+    ByteArray byteArray = new ByteArray(new byte[] { 0x04, 0x12, 0x19, (byte) 0x86 });
+    assertThat(byteArray.toIntArray(), is(new int[] { 0x04121986 }));
+    // number of bytes is more than 4, but less than 8, so anyway 2 ints
+    byteArray = new ByteArray(new byte[] { 0x00, 0x00, 0x00, 0x00, 0x31 });
+    assertThat(byteArray.toIntArray(), is(new int[] { 0x00000000, 0x31000000 }));
+  }
+
+}