diff options
author | Evgeny Mandrikov <mandrikov@gmail.com> | 2011-09-07 15:20:43 +0400 |
---|---|---|
committer | Evgeny Mandrikov <mandrikov@gmail.com> | 2011-09-07 15:41:46 +0400 |
commit | 36bcc8dbc17d720a9d6bb81a36dacd0966341f32 (patch) | |
tree | 4e7ab0e15c840d6d0e31696d8420891217a35826 /sonar-duplications | |
parent | 081adad23e053449b2f187c2e74d481bb1b25feb (diff) | |
download | sonarqube-36bcc8dbc17d720a9d6bb81a36dacd0966341f32.tar.gz sonarqube-36bcc8dbc17d720a9d6bb81a36dacd0966341f32.zip |
SONAR-1091 Update library for detection of duplicates
Diffstat (limited to 'sonar-duplications')
73 files changed, 8125 insertions, 4 deletions
diff --git a/sonar-duplications/pom.xml b/sonar-duplications/pom.xml index f2d5d8ce047..2748a09a385 100644 --- a/sonar-duplications/pom.xml +++ b/sonar-duplications/pom.xml @@ -12,11 +12,16 @@ <dependencies> <dependency> - <groupId>commons-io</groupId> - <artifactId>commons-io</artifactId> - <scope>test</scope> + <groupId>org.codehaus.sonar</groupId> + <artifactId>sonar-channel</artifactId> </dependency> <dependency> + <groupId>com.google.collections</groupId> + <artifactId>google-collections</artifactId> + <version>1.0</version> + </dependency> + + <dependency> <groupId>pmd</groupId> <artifactId>pmd</artifactId> <version>4.2.5</version> @@ -32,5 +37,15 @@ <artifactId>hamcrest-all</artifactId> <scope>test</scope> </dependency> + <dependency> + <groupId>org.mockito</groupId> + <artifactId>mockito-all</artifactId> + <scope>test</scope> + </dependency> + <dependency> + <groupId>ch.qos.logback</groupId> + <artifactId>logback-classic</artifactId> + <scope>test</scope> + </dependency> </dependencies> -</project>
\ No newline at end of file +</project> diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/DuplicationsException.java b/sonar-duplications/src/main/java/org/sonar/duplications/DuplicationsException.java new file mode 100644 index 00000000000..27e7dcdc223 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/DuplicationsException.java @@ -0,0 +1,31 @@ +/* + * 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; + +public class DuplicationsException extends RuntimeException { + + public DuplicationsException(String message) { + super(message); + } + + public DuplicationsException(String message, Throwable cause) { + super(message, cause); + } +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/block/Block.java b/sonar-duplications/src/main/java/org/sonar/duplications/block/Block.java new file mode 100644 index 00000000000..aac5a806ee6 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/block/Block.java @@ -0,0 +1,107 @@ +/* + * 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; + +/** + * Represents part of source code between two lines. + * If two blocks have the same {@link #getBlockHash() hash}, then we assume that there is a duplication in a code, which they represent. + */ +public final class Block { + + private final String resourceId; + private final ByteArray blockHash; + private final int indexInFile; + private final int firstLineNumber; + private final int lastLineNumber; + + /** + * Cache for hash code. + */ + private int hash; + + public Block(String resourceId, ByteArray blockHash, int indexInFile, int firstLineNumber, int lastLineNumber) { + this.resourceId = resourceId; + this.blockHash = blockHash; + this.indexInFile = indexInFile; + this.firstLineNumber = firstLineNumber; + this.lastLineNumber = lastLineNumber; + } + + public Block(int indexInFile, int firstLineNumber, int lastLineNumber, String resourceId, String hash) { + this(resourceId, new ByteArray(hash), indexInFile, firstLineNumber, lastLineNumber); + } + + public String getHashHex() { + return getBlockHash().toString(); + } + + public String getResourceId() { + return resourceId; + } + + public ByteArray getBlockHash() { + return blockHash; + } + + public int getIndexInFile() { + return indexInFile; + } + + public int getFirstLineNumber() { + return firstLineNumber; + } + + public int getLastLineNumber() { + return lastLineNumber; + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof Block)) { + return false; + } + Block other = (Block) obj; + return resourceId.equals(other.resourceId) + && blockHash.equals(other.blockHash) + && indexInFile == other.indexInFile + && firstLineNumber == other.firstLineNumber + && lastLineNumber == other.lastLineNumber; + } + + @Override + public int hashCode() { + int h = hash; + if (h == 0) { + h = resourceId.hashCode(); + h = 31 * h + blockHash.hashCode(); + h = 31 * h + indexInFile; + h = 31 * h + firstLineNumber; + h = 31 * h + lastLineNumber; + hash = h; + } + return h; + } + + @Override + public String toString() { + return "'" + resourceId + "'[" + indexInFile + "|" + firstLineNumber + "-" + lastLineNumber + "]:" + blockHash; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/block/BlockChunker.java b/sonar-duplications/src/main/java/org/sonar/duplications/block/BlockChunker.java new file mode 100644 index 00000000000..2232a3f9a71 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/block/BlockChunker.java @@ -0,0 +1,87 @@ +/* + * 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 java.util.Collections; +import java.util.List; + +import org.sonar.duplications.statement.Statement; + +import com.google.common.collect.Lists; + +/** + * Creates blocks from statements, each block will contain specified number of statements (<code>blockSize</code>) and 64-bits (8-bytes) hash value. + * Hash value computed using + * <a href="http://en.wikipedia.org/wiki/Rolling_hash#Rabin-Karp_rolling_hash">Rabin-Karp rolling hash</a> : + * <blockquote><pre> + * s[0]*31^(blockSize-1) + s[1]*31^(blockSize-2) + ... + s[blockSize-1] + * </pre></blockquote> + * using <code>long</code> arithmetic, where <code>s[i]</code> + * is the hash code of <code>String</code> (which is cached) for statement with number i. + * Thus running time - O(N), where N - number of statements. + * Implementation fully thread-safe. + */ +public class BlockChunker { + + private static final long PRIME_BASE = 31; + + private final int blockSize; + private final long power; + + public BlockChunker(int blockSize) { + this.blockSize = blockSize; + + long pow = 1; + for (int i = 0; i < blockSize - 1; i++) { + pow = pow * PRIME_BASE; + } + this.power = pow; + } + + public List<Block> chunk(String resourceId, List<Statement> statements) { + if (statements.size() < blockSize) { + return Collections.emptyList(); + } + Statement[] statementsArr = statements.toArray(new Statement[statements.size()]); + List<Block> blocks = Lists.newArrayListWithCapacity(statementsArr.length - blockSize + 1); + long hash = 0; + int first = 0; + int last = 0; + for (; last < blockSize - 1; last++) { + hash = hash * PRIME_BASE + statementsArr[last].getValue().hashCode(); + } + for (; last < statementsArr.length; last++, first++) { + Statement firstStatement = statementsArr[first]; + Statement lastStatement = statementsArr[last]; + // add last statement to hash + hash = hash * PRIME_BASE + lastStatement.getValue().hashCode(); + // create block + blocks.add(new Block(resourceId, new ByteArray(hash), first, firstStatement.getStartLine(), lastStatement.getEndLine())); + // remove first statement from hash + hash -= power * firstStatement.getValue().hashCode(); + } + return blocks; + } + + public int getBlockSize() { + return blockSize; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/block/ByteArray.java b/sonar-duplications/src/main/java/org/sonar/duplications/block/ByteArray.java new file mode 100644 index 00000000000..d3d97a19631 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/block/ByteArray.java @@ -0,0 +1,131 @@ +/* + * 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 java.nio.ByteBuffer; +import java.nio.IntBuffer; +import java.util.Arrays; + +/** + * Represents hash for {@link Block}. Immutable. + * + * TODO Godin: would be better to rename to BlockHash, + * also maybe we can incorporate it into Block to reduce memory footprint during detection of duplicates + */ +public final class ByteArray { + + private final byte[] bytes; + + /** + * Cache for hash code. + */ + private int hash; + + public ByteArray(String hexString) { + int len = hexString.length(); + this.bytes = new byte[len / 2]; + for (int i = 0; i < len; i += 2) { + bytes[i / 2] = (byte) ((Character.digit(hexString.charAt(i), 16) << 4) + Character.digit(hexString.charAt(i + 1), 16)); + } + } + + public ByteArray(byte[] bytes) { + this.bytes = new byte[bytes.length]; + System.arraycopy(bytes, 0, this.bytes, 0, bytes.length); + } + + public ByteArray(long value) { + this.bytes = new byte[] { + (byte) (value >>> 56), + (byte) (value >>> 48), + (byte) (value >>> 40), + (byte) (value >>> 32), + (byte) (value >>> 24), + (byte) (value >>> 16), + (byte) (value >>> 8), + (byte) value }; + } + + public ByteArray(int value) { + this.bytes = new byte[] { + (byte) (value >>> 24), + (byte) (value >>> 16), + (byte) (value >>> 8), + (byte) value }; + } + + public ByteArray(int[] intArray) { + ByteBuffer bb = ByteBuffer.allocate(intArray.length * 4); + for (int i : intArray) { + bb.putInt(i); + } + this.bytes = bb.array(); + } + + public int[] toIntArray() { + int size = (bytes.length / 4) + (bytes.length % 4 == 0 ? 0 : 1); // Pad the size to multiple of 4 + ByteBuffer bb = ByteBuffer.allocate(size * 4); + bb.put(bytes); + bb.rewind(); + IntBuffer ib = bb.asIntBuffer(); + int[] result = new int[size]; + ib.get(result); + return result; + } + + private static final String HEXES = "0123456789abcdef"; + + public String toHexString() { + StringBuilder hex = new StringBuilder(2 * bytes.length); + for (byte b : bytes) { + hex.append(HEXES.charAt((b & 0xF0) >> 4)).append(HEXES.charAt((b & 0x0F))); + } + return hex.toString(); + } + + @Override + public String toString() { + return toHexString(); + } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o == null || getClass() != o.getClass()) { + return false; + } + ByteArray other = (ByteArray) o; + return Arrays.equals(bytes, other.bytes); + } + + @Override + public int hashCode() { + int h = hash; + int len = bytes.length; + if (h == 0 && len > 0) { + h = Arrays.hashCode(bytes); + hash = h; + } + return h; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/BlocksGroup.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/BlocksGroup.java new file mode 100644 index 00000000000..55dc41e2298 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/BlocksGroup.java @@ -0,0 +1,212 @@ +/* + * 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.detector.original; + +import java.util.Comparator; +import java.util.List; + +import org.sonar.duplications.block.Block; +import org.sonar.duplications.utils.FastStringComparator; + +import com.google.common.collect.Lists; + +/** + * Set of {@link Block}s, which internally stored as a sorted list. + */ +final class BlocksGroup { + + /** + * Factory method. + * + * @return new empty group + */ + public static BlocksGroup empty() { + return new BlocksGroup(); + } + + protected final List<Block> blocks; + + private BlocksGroup() { + this.blocks = Lists.newArrayList(); + } + + public int size() { + return blocks.size(); + } + + /** + * @return true, if this group subsumed by specified group + * @see #subsumedBy(BlocksGroup, BlocksGroup, int) + */ + public boolean subsumedBy(BlocksGroup other, int indexCorrection) { + return subsumedBy(this, other, indexCorrection); + } + + /** + * @return intersection of this group with specified + * @see #intersect(BlocksGroup, BlocksGroup) + */ + public BlocksGroup intersect(BlocksGroup other) { + return intersect(this, other); + } + + public List<Block[]> pairs(BlocksGroup other, int len) { + return pairs(this, other, len); + } + + /** + * First block from this group with specified resource id. + */ + public Block first(String resourceId) { + for (Block block : blocks) { + if (resourceId.equals(block.getResourceId())) { + return block; + } + } + return null; + } + + @Override + public String toString() { + return blocks.toString(); + } + + /** + * Intersection of two groups is a group, which contains blocks from second group that have corresponding block from first group + * with same resource id and with corrected index. + */ + private static BlocksGroup intersect(BlocksGroup group1, BlocksGroup group2) { + BlocksGroup intersection = new BlocksGroup(); + List<Block> list1 = group1.blocks; + List<Block> list2 = group2.blocks; + int i = 0; + int j = 0; + while (i < list1.size() && j < list2.size()) { + Block block1 = list1.get(i); + Block block2 = list2.get(j); + int c = RESOURCE_ID_COMPARATOR.compare(block1.getResourceId(), block2.getResourceId()); + if (c > 0) { + j++; + continue; + } + if (c < 0) { + i++; + continue; + } + if (c == 0) { + c = block1.getIndexInFile() + 1 - block2.getIndexInFile(); + } + if (c == 0) { // list1[i] == list2[j] + i++; + j++; + intersection.blocks.add(block2); + } + if (c > 0) { // list1[i] > list2[j] + j++; + } + if (c < 0) { // list1[i] < list2[j] + i++; + } + } + return intersection; + } + + /** + * One group is subsumed by another group, when each block from first group has corresponding block from second group + * with same resource id and with corrected index. + */ + private static boolean subsumedBy(BlocksGroup group1, BlocksGroup group2, int indexCorrection) { + List<Block> list1 = group1.blocks; + List<Block> list2 = group2.blocks; + int i = 0; + int j = 0; + while (i < list1.size() && j < list2.size()) { + Block block1 = list1.get(i); + Block block2 = list2.get(j); + int c = RESOURCE_ID_COMPARATOR.compare(block1.getResourceId(), block2.getResourceId()); + if (c != 0) { + j++; + continue; + } + if (c == 0) { + c = block1.getIndexInFile() - indexCorrection - block2.getIndexInFile(); + } + if (c < 0) { // list1[i] < list2[j] + break; + } + if (c != 0) { // list1[i] != list2[j] + j++; + } + if (c == 0) { // list1[i] == list2[j] + i++; + j++; + } + } + return i == list1.size(); + } + + private static List<Block[]> pairs(BlocksGroup beginGroup, BlocksGroup endGroup, int len) { + List<Block[]> result = Lists.newArrayList(); + List<Block> beginBlocks = beginGroup.blocks; + List<Block> endBlocks = endGroup.blocks; + int i = 0; + int j = 0; + while (i < beginBlocks.size() && j < endBlocks.size()) { + Block beginBlock = beginBlocks.get(i); + Block endBlock = endBlocks.get(j); + int c = RESOURCE_ID_COMPARATOR.compare(beginBlock.getResourceId(), endBlock.getResourceId()); + if (c == 0) { + c = beginBlock.getIndexInFile() + len - 1 - endBlock.getIndexInFile(); + } + if (c == 0) { + result.add(new Block[] { beginBlock, endBlock }); + i++; + j++; + } + if (c > 0) { + j++; + } + if (c < 0) { + i++; + } + } + return result; + } + + private static final Comparator<String> RESOURCE_ID_COMPARATOR = FastStringComparator.INSTANCE; + + /** + * Compares {@link Block}s first using {@link Block#getResourceId() resource id} and then using {@link Block#getIndexInFile() index in file}. + */ + public static class BlockComparator implements Comparator<Block> { + + public static final BlockComparator INSTANCE = new BlockComparator(); + + public int compare(Block b1, Block b2) { + int c = RESOURCE_ID_COMPARATOR.compare(b1.getResourceId(), b2.getResourceId()); + if (c == 0) { + return b1.getIndexInFile() - b2.getIndexInFile(); + } + return c; + } + + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java new file mode 100644 index 00000000000..3574b2fed2e --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/Filter.java @@ -0,0 +1,154 @@ +/* + * 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.detector.original; + +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; + +import org.sonar.duplications.index.CloneGroup; +import org.sonar.duplications.index.ClonePart; +import org.sonar.duplications.utils.FastStringComparator; +import org.sonar.duplications.utils.SortedListsUtils; + +import com.google.common.collect.Lists; + +/** + * Performs incremental and brute force algorithm in order to filter clones, which are fully covered by other clones. + * All clones for filtering must be of the same origin - there is no sanity check on this. + * In a worst case it performs O(N*N) comparisons. + * <p> + * Godin: This implementation was chosen because it simple. + * And I wasn't able to find big difference in performance with an interval tree, which we had for the moment of testing. + * Whereas in fact I expected that interval tree would be better for this task. + * Moreover with interval tree we also can use incremental approach, + * but we did not had an implementation with remove operation for the moment of testing. + * </p> + */ +final class Filter { + + /** + * Note that LinkedList should provide better performance here, because of use of operation remove. + * + * @see #add(CloneGroup) + */ + private final List<CloneGroup> filtered = Lists.newLinkedList(); + + /** + * @return current results of filtering + */ + public List<CloneGroup> getResult() { + return filtered; + } + + /** + * Running time - O(N*2*C), where N - number of clones, which was found earlier and C - time of {@link #containsIn(CloneGroup, CloneGroup)}. + */ + public void add(CloneGroup current) { + Iterator<CloneGroup> i = filtered.iterator(); + while (i.hasNext()) { + CloneGroup earlier = i.next(); + // Note that following two conditions cannot be true together - proof by contradiction: + // let C be the current clone and A and B were found earlier + // then since relation is transitive - (A in C) and (C in B) => (A in B) + // so A should be filtered earlier + if (Filter.containsIn(current, earlier)) { + // current clone fully covered by clone, which was found earlier + return; + } + if (Filter.containsIn(earlier, current)) { + // current clone fully covers clone, which was found earlier + i.remove(); + } + } + filtered.add(current); + } + + /** + * Checks that second clone contains first one. + * <p> + * Clone A is contained in another clone B, if every part pA from A has part pB in B, + * which satisfy the conditions: + * <pre> + * (pA.resourceId == pB.resourceId) and (pB.unitStart <= pA.unitStart) and (pA.unitEnd <= pB.unitEnd) + * </pre> + * And all resourcesId from B exactly the same as all resourceId from A, which means that also every part pB from B has part pA in A, + * which satisfy the condition: + * <pre> + * pB.resourceId == pA.resourceId + * </pre> + * So this relation is: + * <ul> + * <li>reflexive - A in A</li> + * <li>transitive - (A in B) and (B in C) => (A in C)</li> + * <li>antisymmetric - (A in B) and (B in A) <=> (A = B)</li> + * </ul> + * </p> + * <p> + * <strong>Important: this method relies on fact that all parts were already sorted by resourceId and unitStart by using + * {@link BlocksGroup.BlockComparator}, which uses {@link FastStringComparator} for comparison by resourceId.</strong> + * </p> + * <p> + * Running time - O(|A|+|B|). + * </p> + */ + static boolean containsIn(CloneGroup first, CloneGroup second) { + if (first.getCloneUnitLength() > second.getCloneUnitLength()) { + return false; + } + List<ClonePart> firstParts = first.getCloneParts(); + List<ClonePart> secondParts = second.getCloneParts(); + return SortedListsUtils.contains(secondParts, firstParts, new ContainsInComparator(first.getCloneUnitLength(), second.getCloneUnitLength())) + && SortedListsUtils.contains(firstParts, secondParts, RESOURCE_ID_COMPARATOR); + } + + private static final Comparator<ClonePart> RESOURCE_ID_COMPARATOR = new Comparator<ClonePart>() { + public int compare(ClonePart o1, ClonePart o2) { + return FastStringComparator.INSTANCE.compare(o1.getResourceId(), o2.getResourceId()); + } + }; + + private static final class ContainsInComparator implements Comparator<ClonePart> { + private final int l1, l2; + + public ContainsInComparator(int l1, int l2) { + this.l1 = l1; + this.l2 = l2; + } + + public int compare(ClonePart o1, ClonePart o2) { + int c = FastStringComparator.INSTANCE.compare(o1.getResourceId(), o2.getResourceId()); + if (c == 0) { + if (o2.getUnitStart() <= o1.getUnitStart()) { + if (o1.getUnitStart() + l1 <= o2.getUnitStart() + l2) { + return 0; // match found - stop search + } else { + return 1; // continue search + } + } else { + return -1; // o1 < o2 by unitStart - stop search + } + } else { + return c; + } + } + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/OriginalCloneDetectionAlgorithm.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/OriginalCloneDetectionAlgorithm.java new file mode 100644 index 00000000000..c6eb043d2b1 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/original/OriginalCloneDetectionAlgorithm.java @@ -0,0 +1,226 @@ +/* + * 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.detector.original; + +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.Map; + +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; +import org.sonar.duplications.index.CloneGroup; +import org.sonar.duplications.index.CloneIndex; +import org.sonar.duplications.index.ClonePart; + +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; + +/** + * Implementation of algorithm described in paper + * <a href="http://www4.in.tum.de/~juergens/publications/icsm2010_crc.pdf">Index-Based Code Clone Detection: Incremental, Distributed, Scalable</a> + * by Benjamin Hummel, Elmar Juergens, Michael Conradt and Lars Heinemann. + */ +public final class OriginalCloneDetectionAlgorithm { + + /** + * Performs detection and returns list of clone groups between file (which represented as a collection of blocks) and index. + * Note that this method ignores blocks for this file, that will be retrieved from index. + */ + public static List<CloneGroup> detect(CloneIndex cloneIndex, Collection<Block> fileBlocks) { + if (fileBlocks.isEmpty()) { + return Collections.EMPTY_LIST; + } + OriginalCloneDetectionAlgorithm reporter = new OriginalCloneDetectionAlgorithm(cloneIndex); + reporter.findClones(fileBlocks); + return reporter.filter.getResult(); + } + + private final CloneIndex cloneIndex; + + private final Filter filter = new Filter(); + + private String originResourceId; + + private OriginalCloneDetectionAlgorithm(CloneIndex cloneIndex) { + this.cloneIndex = cloneIndex; + } + + private BlocksGroup[] createGroups(Collection<Block> fileBlocks) { + // 2: let f be the list of tuples corresponding to filename sorted by statement index + // either read from the index or calculated on the fly + int size = fileBlocks.size(); + + // Godin: create one group per unique hash + Map<ByteArray, BlocksGroup> groupsByHash = Maps.newHashMap(); // TODO Godin: can we create map with expected size? + for (Block fileBlock : fileBlocks) { + ByteArray hash = fileBlock.getBlockHash(); + BlocksGroup sameHash = groupsByHash.get(hash); + if (sameHash == null) { + sameHash = BlocksGroup.empty(); + groupsByHash.put(hash, sameHash); + } + sameHash.blocks.add(fileBlock); + } + + // Godin: retrieve blocks from index + for (Map.Entry<ByteArray, BlocksGroup> entry : groupsByHash.entrySet()) { + ByteArray hash = entry.getKey(); + BlocksGroup group = entry.getValue(); + for (Block blockFromIndex : cloneIndex.getBySequenceHash(hash)) { + // Godin: skip blocks for this file if they come from index + if (!originResourceId.equals(blockFromIndex.getResourceId())) { + group.blocks.add(blockFromIndex); + } + } + Collections.sort(group.blocks, BlocksGroup.BlockComparator.INSTANCE); + } + + // 3: let c be a list with c(0) = empty + BlocksGroup[] sameHashBlocksGroups = new BlocksGroup[size + 2]; + sameHashBlocksGroups[0] = BlocksGroup.empty(); + // 4: for i := 1 to length(f) do + for (Block fileBlock : fileBlocks) { + ByteArray hash = fileBlock.getBlockHash(); + int i = fileBlock.getIndexInFile() + 1; + // 5: retrieve tuples with same sequence hash as f(i) + // 6: store this set as c(i) + sameHashBlocksGroups[i] = groupsByHash.get(hash); + } + + // Godin: allows to report clones at the end of file, because condition at line 13 would be evaluated as true + sameHashBlocksGroups[size + 1] = BlocksGroup.empty(); + + return sameHashBlocksGroups; + } + + private void findClones(Collection<Block> fileBlocks) { + originResourceId = fileBlocks.iterator().next().getResourceId(); + + BlocksGroup[] sameHashBlocksGroups = createGroups(fileBlocks); + + // 7: for i := 1 to length(c) do + for (int i = 1; i < sameHashBlocksGroups.length; i++) { + // In the main loop (starting from Line 7), we first check + // whether any new clones might start at this position. If there + // is only a single tuple with this hash (which has to belong + // to the inspected file at the current location) we skip this loop + // iteration. The same holds if all tuples at position i have already + // been present at position i − 1, as in this case any clone group + // found at position i would be included in a clone group starting + // at position i − 1. + + // Although we use the subset operator in the + // algorithm description, this is not really a subset operation, + // as of course the statement index of the tuples in c(i) will be + // increased by 1 compared to the corresponding ones in c(i − 1) + // and the hash and info fields will differ. + + // 8: if |c(i)| < 2 or c(i) subsumed by c(i - 1) then + if (sameHashBlocksGroups[i].size() < 2 || sameHashBlocksGroups[i].subsumedBy(sameHashBlocksGroups[i - 1], 1)) { + // 9: continue with next loop iteration + continue; + } + + // The set a introduced in Line 10 is called the active set and + // contains all tuples corresponding to clones which have not yet + // been reported. At each iteration of the inner loop the set a + // is reduced to tuples which are also present in c(j); again the + // intersection operator has to account for the increased statement + // index and different hash and info fields. The new value is + // stored in a0. Clones are only reported, if tuples are lost in + // Line 12, as otherwise all current clones could be prolonged + // by one statement. Clone reporting matches tuples that, after + // correction of the statement index, appear in both c(i) and a; + // each matched pair corresponds to a single clone. Its location + // can be extracted from the filename and info fields. + + // 10: let a := c(i) + BlocksGroup currentBlocksGroup = sameHashBlocksGroups[i]; + // 11: for j := i + 1 to length(c) do + for (int j = i + 1; j < sameHashBlocksGroups.length; j++) { + // 12: let a0 := a intersect c(j) + BlocksGroup intersectedBlocksGroup = currentBlocksGroup.intersect(sameHashBlocksGroups[j]); + + // 13: if |a0| < |a| then + if (intersectedBlocksGroup.size() < currentBlocksGroup.size()) { + // 14: report clones from c(i) to a (see text) + + // One problem of this algorithm is that clone classes with + // multiple instances in the same file are encountered and + // reported multiple times. Furthermore, when calculating the clone + // groups for all files in a system, clone groups will be reported + // more than once as well. Both cases can be avoided, by + // checking whether the first element of a0 (with respect to a + // fixed order) is equal to f(j) and only report in this case. + + Block first = currentBlocksGroup.first(originResourceId); + if (first.getIndexInFile() == j - 2) { + // Godin: We report clones, which start in i-1 and end in j-2, so length is j-2-(i-1)+1=j-i + reportClones(sameHashBlocksGroups[i], currentBlocksGroup, j - i); + } + } + // 15: a := a0 + currentBlocksGroup = intersectedBlocksGroup; + + // Line 16 early exits the inner loop if either no more clones are starting + // from position i (i.e., a is too small), or if all tuples from a + // have already been in c(i − 1), corrected for statement index. + // In this case they have already been reported in the previous + // iteration of the outer loop. + + // IMPORTANT Godin: note that difference in indexes between "a" and "c(i-1)" greater than one, + // so method subsumedBy should take this into account + + // 16: if |a| < 2 or a subsumed by c(i-1) then + if (currentBlocksGroup.size() < 2 || currentBlocksGroup.subsumedBy(sameHashBlocksGroups[i - 1], j - i + 1)) { + // 17: break inner loop + break; + } + } + } + } + + private void reportClones(BlocksGroup beginGroup, BlocksGroup endGroup, int cloneLength) { + List<Block[]> pairs = beginGroup.pairs(endGroup, cloneLength); + + ClonePart origin = null; + List<ClonePart> parts = Lists.newArrayList(); + + for (int i = 0; i < pairs.size(); i++) { + Block[] pair = pairs.get(i); + ClonePart part = new ClonePart(pair[0].getResourceId(), pair[0].getIndexInFile(), pair[0].getFirstLineNumber(), pair[1].getLastLineNumber()); + parts.add(part); + + if (originResourceId.equals(part.getResourceId())) { + if (origin == null) { + origin = part; + } else { + if (part.getUnitStart() < origin.getUnitStart()) { + origin = part; + } + } + } + } + + filter.add(new CloneGroup(cloneLength, origin, parts)); + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/AbstractCloneIndex.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/AbstractCloneIndex.java new file mode 100644 index 00000000000..88ec3bad6d2 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/AbstractCloneIndex.java @@ -0,0 +1,24 @@ +/* + * 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.index; + +public abstract class AbstractCloneIndex implements CloneIndex { + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/CloneGroup.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/CloneGroup.java new file mode 100644 index 00000000000..f6552237322 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/CloneGroup.java @@ -0,0 +1,107 @@ +/* + * 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.index; + +import java.util.List; + +import com.google.common.collect.ImmutableList; + +/** + * Groups a set of related {@link ClonePart}s. + */ +public class CloneGroup { + + private final ClonePart originPart; + private final int cloneLength; + private final List<ClonePart> parts; + + /** + * Cache for hash code. + */ + private int hash; + + public CloneGroup(int cloneLength, ClonePart origin, List<ClonePart> parts) { + this.cloneLength = cloneLength; + this.originPart = origin; + this.parts = ImmutableList.copyOf(parts); + } + + public ClonePart getOriginPart() { + return originPart; + } + + /** + * @return clone length in units (not in lines) + */ + public int getCloneUnitLength() { + return cloneLength; + } + + public List<ClonePart> getCloneParts() { + return parts; + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + for (ClonePart part : parts) { + builder.append(part).append(" - "); + } + builder.append(cloneLength); + return builder.toString(); + } + + /** + * Two groups are equal, if they have same length, same origins and contain same parts in same order. + */ + @Override + public boolean equals(Object object) { + if (!(object instanceof CloneGroup)) { + return false; + } + CloneGroup another = (CloneGroup) object; + if (another.cloneLength != cloneLength || parts.size() != another.parts.size()) { + return false; + } + if (!originPart.equals(another.originPart)) { + return false; + } + boolean result = true; + for (int i = 0; i < parts.size(); i++) { + result &= another.parts.get(i).equals(parts.get(i)); + } + return result; + } + + @Override + public int hashCode() { + int h = hash; + if (h == 0 && cloneLength != 0) { + for (ClonePart part : parts) { + h = 31 * h + part.hashCode(); + } + h = 31 * h + originPart.hashCode(); + h = 31 * h + cloneLength; + hash = h; + } + return h; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/CloneIndex.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/CloneIndex.java new file mode 100644 index 00000000000..b06f6775c42 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/CloneIndex.java @@ -0,0 +1,48 @@ +/* + * 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.index; + +import java.util.Collection; + +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; + +public interface CloneIndex { + + /** + * Performs search of blocks for specified resource. + * + * @return collection of blocks from index for specified resource and empty collection if nothing found + */ + Collection<Block> getByResourceId(String resourceId); + + /** + * Performs search of blocks for specified hash value. + * + * @return collection of blocks from index with specified hash and empty collection if nothing found + */ + Collection<Block> getBySequenceHash(ByteArray hash); + + /** + * Adds specified block into index. + */ + void insert(Block block); + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/ClonePart.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/ClonePart.java new file mode 100644 index 00000000000..2f31bf6f93a --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/ClonePart.java @@ -0,0 +1,91 @@ +/* + * 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.index; + +public class ClonePart { + + private final String resourceId; + private final int unitStart; + private final int lineStart; + private final int lineEnd; + + /** + * Cache for hash code. + */ + private int hash; + + public ClonePart(String resourceId, int unitStart, int lineStart, int lineEnd) { + this.resourceId = resourceId; + this.unitStart = unitStart; + this.lineStart = lineStart; + this.lineEnd = lineEnd; + } + + public String getResourceId() { + return resourceId; + } + + public int getUnitStart() { + return unitStart; + } + + public int getLineStart() { + return lineStart; + } + + public int getLineEnd() { + return lineEnd; + } + + public int getLines() { + return lineEnd - lineStart + 1; + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof ClonePart) { + ClonePart another = (ClonePart) obj; + return another.resourceId.equals(resourceId) + && another.lineStart == lineStart + && another.lineEnd == lineEnd + && another.unitStart == unitStart; + } + return false; + } + + @Override + public int hashCode() { + int h = hash; + if (h == 0) { + h = resourceId.hashCode(); + h = 31 * h + lineStart; + h = 31 * h + lineEnd; + h = 31 * h + unitStart; + hash = h; + } + return h; + } + + @Override + public String toString() { + return "'" + resourceId + "':[" + unitStart + "|" + lineStart + "-" + lineEnd + "]"; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/DataUtils.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/DataUtils.java new file mode 100644 index 00000000000..65eb1dbb692 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/DataUtils.java @@ -0,0 +1,116 @@ +/* + * 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.index; + +public final class DataUtils { + + public interface Sortable { + + /** + * @return the number of elements. + */ + int size(); + + /** + * Swaps elements in positions i and j. + */ + void swap(int i, int j); + + /** + * @return true if element in position i less than in position j. + */ + boolean isLess(int i, int j); + + } + + /** + * Value for search must be stored in position {@link Sortable#size() size}. + */ + public static int binarySearch(Sortable data) { + int value = data.size(); + int lower = 0; + int upper = data.size(); + while (lower < upper) { + int mid = (lower + upper) >> 1; + if (data.isLess(mid, value)) { + lower = mid + 1; + } else { + upper = mid; + } + } + return lower; + } + + public static void sort(Sortable data) { + quickSort(data, 0, data.size() - 1); + } + + private static void bubbleSort(Sortable data, int left, int right) { + for (int i = right; i > left; i--) { + for (int j = left; j < i; j++) { + if (data.isLess(j + 1, j)) { + data.swap(j, j + 1); + } + } + } + } + + private static int partition(Sortable data, int i, int j) { + // can be selected randomly + int pivot = i + (j - i) / 2; + while (i <= j) { + while (data.isLess(i, pivot)) { + i++; + } + while (data.isLess(pivot, j)) { + j--; + } + if (i <= j) { + data.swap(i, j); + if (i == pivot) { + pivot = j; + } else if (j == pivot) { + pivot = i; + } + i++; + j--; + } + } + return i; + } + + private static void quickSort(Sortable data, int low, int high) { + if (high - low < 5) { + bubbleSort(data, low, high); + return; + } + int i = partition(data, low, high); + if (low < i - 1) { + quickSort(data, low, i - 1); + } + if (i < high) { + quickSort(data, i, high); + } + } + + private DataUtils() { + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/MemoryCloneIndex.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/MemoryCloneIndex.java new file mode 100644 index 00000000000..1fbce94e817 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/MemoryCloneIndex.java @@ -0,0 +1,84 @@ +/* + * 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.index; + +import java.io.Serializable; +import java.util.Collection; +import java.util.Comparator; + +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; + +import com.google.common.collect.HashMultimap; +import com.google.common.collect.TreeMultimap; + +public class MemoryCloneIndex implements CloneIndex { + + private final TreeMultimap<String, Block> filenameIndex; + private final HashMultimap<ByteArray, Block> sequenceHashIndex; + + private static final class ValueComparator implements Comparator<Block>, Serializable { + + private static final long serialVersionUID = 6048010242032502222L; + + public int compare(Block o1, Block o2) { + if (o2.getResourceId().equals(o1.getResourceId())) { + return o1.getIndexInFile() - o2.getIndexInFile(); + } + return o1.getResourceId().compareTo(o2.getResourceId()); + } + } + + private static final class KeyComparator implements Comparator<String>, Serializable { + + private static final long serialVersionUID = 8705841881237170539L; + + public int compare(String o1, String o2) { + return o1.compareTo(o2); + } + } + + public MemoryCloneIndex() { + filenameIndex = TreeMultimap.create(new KeyComparator(), new ValueComparator()); + sequenceHashIndex = HashMultimap.create(); + } + + public Collection<String> getAllUniqueResourceId() { + return filenameIndex.keySet(); + } + + public boolean containsResourceId(String resourceId) { + return filenameIndex.containsKey(resourceId); + } + + public Collection<Block> getByResourceId(String fileName) { + return filenameIndex.get(fileName); + } + + public Collection<Block> getBySequenceHash(ByteArray sequenceHash) { + return sequenceHashIndex.get(sequenceHash); + } + + public void insert(Block tuple) { + filenameIndex.put(tuple.getResourceId(), tuple); + sequenceHashIndex.put(tuple.getBlockHash(), tuple); + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/MemoryCloneIndex2.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/MemoryCloneIndex2.java new file mode 100644 index 00000000000..ae4e9c35da4 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/MemoryCloneIndex2.java @@ -0,0 +1,65 @@ +/* + * 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.index; + +import java.util.Collection; +import java.util.Collections; +import java.util.List; +import java.util.Map; + +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; + +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; + +public class MemoryCloneIndex2 extends AbstractCloneIndex { + + private Map<String, List<Block>> byResource = Maps.newHashMap(); + private Map<ByteArray, List<Block>> byHash = Maps.newHashMap(); + + public Collection<Block> getByResourceId(String resourceId) { + return get(byResource, resourceId); + } + + public Collection<Block> getBySequenceHash(ByteArray sequenceHash) { + return get(byHash, sequenceHash); + } + + public void insert(Block block) { + put(byResource, block.getResourceId(), block); + put(byHash, block.getBlockHash(), block); + } + + private static <T> List<Block> get(Map<T, List<Block>> map, T key) { + List<Block> blocks = map.get(key); + return blocks != null ? blocks : Collections.EMPTY_LIST; + } + + private static <T> void put(Map<T, List<Block>> map, T key, Block value) { + List<Block> blocks = map.get(key); + if (blocks == null) { + blocks = Lists.newLinkedList(); + map.put(key, blocks); + } + blocks.add(value); + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/index/PackedMemoryCloneIndex.java b/sonar-duplications/src/main/java/org/sonar/duplications/index/PackedMemoryCloneIndex.java new file mode 100644 index 00000000000..c19bbfdd042 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/index/PackedMemoryCloneIndex.java @@ -0,0 +1,280 @@ +/* + * 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.index; + +import java.util.Collection; +import java.util.List; + +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; +import org.sonar.duplications.utils.FastStringComparator; + +import com.google.common.collect.Lists; + +/** + * Provides an index optimized by memory. + * <p> + * Each object in Java has an overhead - see + * <a href="http://devblog.streamy.com/2009/07/24/determine-size-of-java-object-class/">"HOWTO: Determine the size of a Java Object or Class"</a>. + * So to optimize memory consumption, we use flat arrays, however this increases time of queries. + * During usual detection of duplicates most time consuming method is a {@link #getByResourceId(String)}: + * around 50% of time spent in this class and number of invocations of this method is 1% of total invocations, + * however total time spent in this class less than 1 second for small projects and around 2 seconds for projects like JDK. + * </p> + * <p> + * Note that this implementation currently does not support deletion, however it's possible to implement. + * </p> + */ +public class PackedMemoryCloneIndex extends AbstractCloneIndex { + + private static final int DEFAULT_INITIAL_CAPACITY = 1024; + + private static final int BLOCK_INTS = 3; + + private final int hashInts; + + private final int blockInts; + + /** + * Indicates that index requires sorting to perform queries. + */ + private boolean sorted; + + /** + * Current number of blocks in index. + */ + private int size; + + private String[] resourceIds; + private int[] blockData; + + private int[] resourceIdsIndex; + + public PackedMemoryCloneIndex() { + this(8, DEFAULT_INITIAL_CAPACITY); + } + + /** + * @param hashBytes size of hash in bytes + * @param initialCapacity the initial capacity + */ + public PackedMemoryCloneIndex(int hashBytes, int initialCapacity) { + this.sorted = false; + this.hashInts = hashBytes / 4; + this.blockInts = hashInts + BLOCK_INTS; + this.size = 0; + this.resourceIds = new String[initialCapacity]; + this.blockData = new int[initialCapacity * blockInts]; + this.resourceIdsIndex = new int[initialCapacity]; + } + + /** + * {@inheritDoc} + * <p> + * <strong>Note that this implementation does not guarantee that blocks would be sorted by index.</strong> + * </p> + */ + public Collection<Block> getByResourceId(String resourceId) { + ensureSorted(); + + // prepare resourceId for binary search + resourceIds[size] = resourceId; + resourceIdsIndex[size] = size; + + int index = DataUtils.binarySearch(byResourceId); + + List<Block> result = Lists.newArrayList(); + int realIndex = resourceIdsIndex[index]; + while (index < size && FastStringComparator.INSTANCE.compare(resourceIds[realIndex], resourceId) == 0) { + // extract block (note that there is no need to extract resourceId) + int offset = realIndex * blockInts; + int[] hash = new int[hashInts]; + for (int j = 0; j < hashInts; j++) { + hash[j] = blockData[offset++]; + } + int indexInFile = blockData[offset++]; + int firstLineNumber = blockData[offset++]; + int lastLineNumber = blockData[offset]; + + result.add(new Block(resourceId, new ByteArray(hash), indexInFile, firstLineNumber, lastLineNumber)); + + index++; + realIndex = resourceIdsIndex[index]; + } + return result; + } + + /** + * {@inheritDoc} + */ + public Collection<Block> getBySequenceHash(ByteArray sequenceHash) { + ensureSorted(); + + // prepare hash for binary search + int[] hash = sequenceHash.toIntArray(); + if (hash.length != hashInts) { + throw new IllegalArgumentException("Expected " + hashInts + " ints in hash, but got " + hash.length); + } + int offset = size * blockInts; + for (int i = 0; i < hashInts; i++) { + blockData[offset++] = hash[i]; + } + + int index = DataUtils.binarySearch(byBlockHash); + + List<Block> result = Lists.newArrayList(); + while (index < size && !isLessByHash(size, index)) { + // extract block (note that there is no need to extract hash) + String resourceId = resourceIds[index]; + offset = index * blockInts + hashInts; + int indexInFile = blockData[offset++]; + int firstLineNumber = blockData[offset++]; + int lastLineNumber = blockData[offset]; + + result.add(new Block(resourceId, sequenceHash, indexInFile, firstLineNumber, lastLineNumber)); + index++; + } + return result; + } + + /** + * {@inheritDoc} + * <p> + * <strong>Note that this implementation allows insertion of two blocks with same index for one resource.</strong> + * </p> + */ + public void insert(Block block) { + sorted = false; + ensureCapacity(); + + resourceIds[size] = block.getResourceId(); + + int[] hash = block.getBlockHash().toIntArray(); + if (hash.length != hashInts) { + throw new IllegalArgumentException("Expected " + hashInts + " ints in hash, but got " + hash.length); + } + int offset = size * blockInts; + for (int i = 0; i < hashInts; i++) { + blockData[offset++] = hash[i]; + } + blockData[offset++] = block.getIndexInFile(); + blockData[offset++] = block.getFirstLineNumber(); + blockData[offset] = block.getLastLineNumber(); + + size++; + } + + /** + * Increases the capacity, if necessary. + */ + private void ensureCapacity() { + if (size < resourceIds.length) { + return; + } + int newCapacity = (resourceIds.length * 3) / 2 + 1; + // Increase size of resourceIds + String[] oldResourceIds = resourceIds; + resourceIds = new String[newCapacity]; + System.arraycopy(oldResourceIds, 0, resourceIds, 0, oldResourceIds.length); + // Increase size of blockData + int[] oldBlockData = blockData; + blockData = new int[newCapacity * blockInts]; + System.arraycopy(oldBlockData, 0, blockData, 0, oldBlockData.length); + // Increase size of byResourceIndices (no need to copy old, because would be restored in method ensureSorted) + resourceIdsIndex = new int[newCapacity]; + sorted = false; + } + + /** + * Performs sorting, if necessary. + */ + private void ensureSorted() { + if (sorted) { + return; + } + + ensureCapacity(); + + DataUtils.sort(byBlockHash); + for (int i = 0; i < size; i++) { + resourceIdsIndex[i] = i; + } + DataUtils.sort(byResourceId); + + sorted = true; + } + + private boolean isLessByHash(int i, int j) { + i *= blockInts; + j *= blockInts; + for (int k = 0; k < hashInts; k++, i++, j++) { + if (blockData[i] < blockData[j]) { + return true; + } + if (blockData[i] > blockData[j]) { + return false; + } + } + return false; + } + + private final DataUtils.Sortable byBlockHash = new DataUtils.Sortable() { + public void swap(int i, int j) { + String tmp = resourceIds[i]; + resourceIds[i] = resourceIds[j]; + resourceIds[j] = tmp; + + i *= blockInts; + j *= blockInts; + for (int k = 0; k < blockInts; k++, i++, j++) { + int x = blockData[i]; + blockData[i] = blockData[j]; + blockData[j] = x; + } + } + + public boolean isLess(int i, int j) { + return isLessByHash(i, j); + } + + public int size() { + return size; + } + }; + + private final DataUtils.Sortable byResourceId = new DataUtils.Sortable() { + public void swap(int i, int j) { + int tmp = resourceIdsIndex[i]; + resourceIdsIndex[i] = resourceIdsIndex[j]; + resourceIdsIndex[j] = tmp; + } + + public boolean isLess(int i, int j) { + String s1 = resourceIds[resourceIdsIndex[i]]; + String s2 = resourceIds[resourceIdsIndex[j]]; + return FastStringComparator.INSTANCE.compare(s1, s2) < 0; + } + + public int size() { + return size; + } + }; + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/java/JavaStatementBuilder.java b/sonar-duplications/src/main/java/org/sonar/duplications/java/JavaStatementBuilder.java new file mode 100644 index 00000000000..99a74d26927 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/java/JavaStatementBuilder.java @@ -0,0 +1,50 @@ +/* + * 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.java; + +import org.sonar.duplications.statement.StatementChunker; + +import static org.sonar.duplications.statement.TokenMatcherFactory.*; + +public final class JavaStatementBuilder { + + private JavaStatementBuilder() { + } + + public static StatementChunker build() { + return StatementChunker.builder() + .ignore(from("import"), to(";")) + .ignore(from("package"), to(";")) + .ignore(token("}")) + .ignore(token("{")) + .statement(from("@"), anyToken(), opt(bridge("(", ")"))) + .statement(from("do")) + .statement(from("if"), bridge("(", ")")) + .statement(from("else"), token("if"), bridge("(", ")")) + .statement(from("else")) + .statement(from("for"), bridge("(", ")")) + .statement(from("while"), bridge("(", ")")) + .statement(from("case"), to(":")) + .statement(from("default"), to(":")) + .statement(to(";", "{", "}"), forgetLastToken()) + .build(); + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/java/JavaTokenProducer.java b/sonar-duplications/src/main/java/org/sonar/duplications/java/JavaTokenProducer.java new file mode 100644 index 00000000000..d9d922fcb27 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/java/JavaTokenProducer.java @@ -0,0 +1,74 @@ +/* + * 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.java; + +import org.sonar.duplications.token.TokenChunker; + +/** + * See <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html">The Java Language Specification, Third Edition: Lexical Structure</a> + * + * <p> + * We decided to use dollar sign as a prefix for normalization, even if it can be a part of an identifier, + * because according to Java Language Specification it supposed to be used only in mechanically generated source code. + * Thus probability to find it within a normal code should be low. + * </p> + */ +public final class JavaTokenProducer { + + private JavaTokenProducer() { + } + + private static final String NORMALIZED_CHARACTER_LITERAL = "$CHARS"; + private static final String NORMALIZED_NUMERIC_LITERAL = "$NUMBER"; + + private static final String EXP = "([Ee][+-]?+[0-9]++)"; + private static final String BINARY_EXP = "([Pp][+-]?+[0-9]++)"; + + private static final String FLOAT_SUFFIX = "[fFdD]"; + private static final String INT_SUFFIX = "[lL]"; + + public static TokenChunker build() { + return TokenChunker.builder() + // White Space + .ignore("\\s") + // Comments + .ignore("//[^\\n\\r]*+") + .ignore("/\\*[\\s\\S]*?\\*/") + // String Literals + .token("\"([^\"\\\\]*+(\\\\[\\s\\S])?+)*+\"", NORMALIZED_CHARACTER_LITERAL) + // Character Literals + .token("'([^'\\n\\\\]*+(\\\\.)?+)*+'", NORMALIZED_CHARACTER_LITERAL) + // Identifiers, Keywords, Boolean Literals, The Null Literal + .token("\\p{javaJavaIdentifierStart}++\\p{javaJavaIdentifierPart}*+") + // Floating-Point Literals + .token("[0-9]++\\.([0-9]++)?+" + EXP + "?+" + FLOAT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + .token("\\.[0-9]++" + EXP + "?+" + FLOAT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + .token("[0-9]++" + EXP + FLOAT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + .token("0[xX][0-9a-fA-F]++\\.[0-9a-fA-F]*+" + BINARY_EXP + "?+" + FLOAT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + .token("0[xX][0-9a-fA-F]++" + BINARY_EXP + FLOAT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + // Integer Literals + .token("0[xX][0-9a-fA-F]++" + INT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + .token("[0-9]++" + INT_SUFFIX + "?+", NORMALIZED_NUMERIC_LITERAL) + // Any other character + .token(".") + .build(); + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/Statement.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/Statement.java new file mode 100644 index 00000000000..224e9a7c01d --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/Statement.java @@ -0,0 +1,96 @@ +/* + * 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.statement; + +import java.util.List; + +import org.sonar.duplications.token.Token; + +public class Statement { + + private final int startLine; + private final int endLine; + private final String value; + + /** + * Cache for hash code. + */ + private int hash; + + public Statement(int startLine, int endLine, String value) { + this.startLine = startLine; + this.endLine = endLine; + this.value = value; + } + + public Statement(List<Token> tokens) { + if (tokens == null || tokens.isEmpty()) { + throw new IllegalArgumentException("A statement can't be initialized with an empty list of tokens"); + } + StringBuilder sb = new StringBuilder(); + for (Token token : tokens) { + sb.append(token.getValue()); + } + this.value = sb.toString(); + this.startLine = tokens.get(0).getLine(); + this.endLine = tokens.get(tokens.size() - 1).getLine(); + } + + public int getStartLine() { + return startLine; + } + + public int getEndLine() { + return endLine; + } + + public String getValue() { + return value; + } + + @Override + public int hashCode() { + int h = hash; + if (h == 0) { + h = value.hashCode(); + h = 31 * h + startLine; + h = 31 * h + endLine; + hash = h; + } + return h; + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof Statement)) { + return false; + } + Statement other = (Statement) obj; + return startLine == other.startLine + && endLine == other.endLine + && value.equals(other.value); + } + + @Override + public String toString() { + return "[" + getStartLine() + "-" + getEndLine() + "] [" + getValue() + "]"; + } + +}
\ No newline at end of file diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChannel.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChannel.java new file mode 100644 index 00000000000..fe12fdf7c76 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChannel.java @@ -0,0 +1,67 @@ +/* + * 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.statement; + +import java.util.ArrayList; +import java.util.List; + +import org.sonar.duplications.statement.matcher.TokenMatcher; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public final class StatementChannel { + + private final TokenMatcher[] tokenMatchers; + private final boolean blackHole; + + public static StatementChannel create(TokenMatcher... tokenMatchers) { + return new StatementChannel(false, tokenMatchers); + } + + public static StatementChannel createBlackHole(TokenMatcher... tokenMatchers) { + return new StatementChannel(true, tokenMatchers); + } + + private StatementChannel(boolean blackHole, TokenMatcher... tokenMatchers) { + if (tokenMatchers == null || tokenMatchers.length == 0) { + throw new IllegalArgumentException(); + } + this.blackHole = blackHole; + this.tokenMatchers = tokenMatchers; + } + + public boolean consume(TokenQueue tokenQueue, List<Statement> output) { + List<Token> matchedTokenList = new ArrayList<Token>(); + for (TokenMatcher tokenMatcher : tokenMatchers) { + if (!tokenMatcher.matchToken(tokenQueue, matchedTokenList)) { + tokenQueue.pushForward(matchedTokenList); + return false; + } + } + + // all matchers were successful, so now build the statement + // matchedTokenList.size() check is for case with ForgiveLastTokenMatcher + if (!blackHole && !matchedTokenList.isEmpty()) { + output.add(new Statement(matchedTokenList)); + } + return true; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChannelDisptacher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChannelDisptacher.java new file mode 100644 index 00000000000..c6020857636 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChannelDisptacher.java @@ -0,0 +1,54 @@ +/* + * 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.statement; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class StatementChannelDisptacher { + + private final StatementChannel[] channels; + + public StatementChannelDisptacher(List<StatementChannel> channels) { + this.channels = channels.toArray(new StatementChannel[channels.size()]); + } + + public boolean consume(TokenQueue tokenQueue, List<Statement> statements) { + Token nextToken = tokenQueue.peek(); + while (nextToken != null) { + boolean channelConsumed = false; + for (StatementChannel channel : channels) { + if (channel.consume(tokenQueue, statements)) { + channelConsumed = true; + break; + } + } + if (!channelConsumed) { + throw new IllegalStateException("None of the statement channel has been able to consume token: " + nextToken); + } + nextToken = tokenQueue.peek(); + } + return true; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChunker.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChunker.java new file mode 100644 index 00000000000..aeced1283b1 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/StatementChunker.java @@ -0,0 +1,95 @@ +/* + * 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.statement; + +import java.util.ArrayList; +import java.util.List; + +import org.sonar.duplications.DuplicationsException; +import org.sonar.duplications.statement.matcher.TokenMatcher; +import org.sonar.duplications.token.TokenQueue; + +public final class StatementChunker { + + private final StatementChannelDisptacher channelDispatcher; + + public static Builder builder() { + return new Builder(); + } + + private StatementChunker(Builder builder) { + this.channelDispatcher = builder.getChannelDispatcher(); + } + + public List<Statement> chunk(TokenQueue tokenQueue) { + if (tokenQueue == null) { + throw new IllegalArgumentException(); + } + List<Statement> statements = new ArrayList<Statement>(); + try { + channelDispatcher.consume(tokenQueue, statements); + return statements; + } catch (Exception e) { + throw new DuplicationsException("Unable to build statement from token : " + tokenQueue.peek(), e); + } + } + + /** + * Note that order is important, e.g. + * <code>statement(token(A)).ignore(token(A))</code> for the input sequence "A" will produce statement, whereas + * <code>ignore(token(A)).statement(token(A))</code> will not. + */ + public static final class Builder { + + private List<StatementChannel> channels = new ArrayList<StatementChannel>(); + + private Builder() { + } + + public StatementChunker build() { + return new StatementChunker(this); + } + + /** + * Defines that sequence of tokens must be ignored, if it matches specified list of matchers. + * + * @see TokenMatcherFactory + */ + public Builder ignore(TokenMatcher... matchers) { + channels.add(StatementChannel.createBlackHole(matchers)); + return this; + } + + /** + * Defines that sequence of tokens, which is matched specified list of matchers, is a statement. + * + * @see TokenMatcherFactory + */ + public Builder statement(TokenMatcher... matchers) { + channels.add(StatementChannel.create(matchers)); + return this; + } + + private StatementChannelDisptacher getChannelDispatcher() { + return new StatementChannelDisptacher(channels); + } + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/TokenMatcherFactory.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/TokenMatcherFactory.java new file mode 100644 index 00000000000..7f0b3e15a10 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/TokenMatcherFactory.java @@ -0,0 +1,65 @@ +/* + * 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.statement; + +import org.sonar.duplications.statement.matcher.AnyTokenMatcher; +import org.sonar.duplications.statement.matcher.BridgeTokenMatcher; +import org.sonar.duplications.statement.matcher.ExactTokenMatcher; +import org.sonar.duplications.statement.matcher.ForgetLastTokenMatcher; +import org.sonar.duplications.statement.matcher.OptTokenMatcher; +import org.sonar.duplications.statement.matcher.TokenMatcher; +import org.sonar.duplications.statement.matcher.UptoTokenMatcher; + +public final class TokenMatcherFactory { + + private TokenMatcherFactory() { + } + + public static TokenMatcher from(String token) { + return new ExactTokenMatcher(token); + } + + public static TokenMatcher to(String... tokens) { + return new UptoTokenMatcher(tokens); + } + + public static TokenMatcher bridge(String lToken, String rToken) { + return new BridgeTokenMatcher(lToken, rToken); + } + + public static TokenMatcher anyToken() { + // TODO Godin: we can return singleton instance + return new AnyTokenMatcher(); + } + + public static TokenMatcher opt(TokenMatcher optMatcher) { + return new OptTokenMatcher(optMatcher); + } + + public static TokenMatcher forgetLastToken() { + // TODO Godin: we can return singleton instance + return new ForgetLastTokenMatcher(); + } + + public static TokenMatcher token(String token) { + return new ExactTokenMatcher(token); + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/AnyTokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/AnyTokenMatcher.java new file mode 100644 index 00000000000..44fd0db7f3e --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/AnyTokenMatcher.java @@ -0,0 +1,41 @@ +/* + * 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.statement.matcher; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +/** + * Consumes any token, but only one. + */ +public class AnyTokenMatcher extends TokenMatcher { + + /** + * @return always true + */ + @Override + public boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList) { + matchedTokenList.add(tokenQueue.poll()); + return true; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/BridgeTokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/BridgeTokenMatcher.java new file mode 100644 index 00000000000..490848e9f04 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/BridgeTokenMatcher.java @@ -0,0 +1,64 @@ +/* + * 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.statement.matcher; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +/** + * Consumes everything between pair of tokens. + */ +public class BridgeTokenMatcher extends TokenMatcher { + + private final String lToken; + private final String rToken; + + public BridgeTokenMatcher(String lToken, String rToken) { + if (lToken == null || rToken == null) { + throw new IllegalArgumentException(); + } + this.lToken = lToken; + this.rToken = rToken; + } + + @Override + public boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList) { + if (!tokenQueue.isNextTokenValue(lToken)) { + return false; + } + int stack = 0; + while (tokenQueue.peek() != null) { + Token token = tokenQueue.poll(); + if (lToken.equals(token.getValue())) { + stack++; + } else if (rToken.equals(token.getValue())) { + stack--; + } + matchedTokenList.add(token); + if (stack == 0) { + return true; + } + } + return false; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/ExactTokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/ExactTokenMatcher.java new file mode 100644 index 00000000000..a21b8ba8c82 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/ExactTokenMatcher.java @@ -0,0 +1,50 @@ +/* + * 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.statement.matcher; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +/** + * Consumes only one specified token. + */ +public class ExactTokenMatcher extends TokenMatcher { + + private final String tokenToMatch; + + public ExactTokenMatcher(String tokenToMatch) { + if (tokenToMatch == null) { + throw new IllegalArgumentException(); + } + this.tokenToMatch = tokenToMatch; + } + + @Override + public boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList) { + if (tokenQueue.isNextTokenValue(tokenToMatch)) { + matchedTokenList.add(tokenQueue.poll()); + return true; + } + return false; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/ForgetLastTokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/ForgetLastTokenMatcher.java new file mode 100644 index 00000000000..06a8e7d801e --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/ForgetLastTokenMatcher.java @@ -0,0 +1,41 @@ +/* + * 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.statement.matcher; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +/** + * Forgets token, which was consumed last. + */ +public class ForgetLastTokenMatcher extends TokenMatcher { + + /** + * @return always true + */ + @Override + public boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList) { + matchedTokenList.remove(matchedTokenList.size() - 1); + return true; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/OptTokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/OptTokenMatcher.java new file mode 100644 index 00000000000..a76ad0fdc0f --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/OptTokenMatcher.java @@ -0,0 +1,50 @@ +/* + * 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.statement.matcher; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +/** + * Delegates consumption to another matcher. + */ +public class OptTokenMatcher extends TokenMatcher { + + private final TokenMatcher matcher; + + public OptTokenMatcher(TokenMatcher matcher) { + if (matcher == null) { + throw new IllegalArgumentException(); + } + this.matcher = matcher; + } + + /** + * @return always true + */ + @Override + public boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList) { + matcher.matchToken(tokenQueue, matchedTokenList); + return true; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/TokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/TokenMatcher.java new file mode 100644 index 00000000000..4bc576e761a --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/TokenMatcher.java @@ -0,0 +1,36 @@ +/* + * 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.statement.matcher; + +import java.util.List; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public abstract class TokenMatcher { + + /** + * @param tokenQueue queue of tokens for consumption, which contains at least one element + * @param matchedTokenList list to populate by tokens, which were consumed + * @return true if tokens were consumed successfully + */ + public abstract boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList); + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/UptoTokenMatcher.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/UptoTokenMatcher.java new file mode 100644 index 00000000000..729d8a4b064 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/matcher/UptoTokenMatcher.java @@ -0,0 +1,61 @@ +/* + * 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.statement.matcher; + +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +/** + * Consumes everything up to one of the specified tokens. + */ +public class UptoTokenMatcher extends TokenMatcher { + + private final Set<String> uptoMatchTokens = new HashSet<String>(); + + public UptoTokenMatcher(String[] uptoMatchTokens) { + if (uptoMatchTokens == null) { + throw new IllegalArgumentException(); + } + if (uptoMatchTokens.length == 0) { + // otherwise we will always try to consume everything, but will never succeed + throw new IllegalArgumentException(); + } + for (String uptoMatchToken : uptoMatchTokens) { + this.uptoMatchTokens.add(uptoMatchToken); + } + } + + @Override + public boolean matchToken(TokenQueue tokenQueue, List<Token> matchedTokenList) { + do { + Token token = tokenQueue.poll(); + matchedTokenList.add(token); + if (uptoMatchTokens.contains(token.getValue())) { + return true; + } + } while (tokenQueue.peek() != null); + return false; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/statement/package-info.java b/sonar-duplications/src/main/java/org/sonar/duplications/statement/package-info.java new file mode 100644 index 00000000000..176f1c5df22 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/statement/package-info.java @@ -0,0 +1,27 @@ +/* + * 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 + */ + +/** + * Provides a basic framework to create list of statements from list of tokens. + * + * The entry point of this framework is the {@link org.sonar.duplications.statement.StatementChunker} class. + */ +package org.sonar.duplications.statement; + diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/token/BlackHoleTokenChannel.java b/sonar-duplications/src/main/java/org/sonar/duplications/token/BlackHoleTokenChannel.java new file mode 100644 index 00000000000..560bce4301e --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/token/BlackHoleTokenChannel.java @@ -0,0 +1,35 @@ +/* + * 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.token; + +import org.sonar.channel.RegexChannel; + +class BlackHoleTokenChannel extends RegexChannel<TokenQueue> { + + public BlackHoleTokenChannel(String regex) { + super(regex); + } + + @Override + protected void consume(CharSequence token, TokenQueue output) { + // do nothing + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/token/Token.java b/sonar-duplications/src/main/java/org/sonar/duplications/token/Token.java new file mode 100644 index 00000000000..aa251d8b84f --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/token/Token.java @@ -0,0 +1,77 @@ +/* + * 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.token; + +public class Token { + + private final int line; + private final int column; + private final String value; + + /** + * Cache for hash code. + */ + private int hash; + + public Token(String value, int line, int column) { + this.value = value; + this.column = column; + this.line = line; + } + + public int getLine() { + return line; + } + + public int getColumn() { + return column; + } + + public String getValue() { + return value; + } + + @Override + public boolean equals(Object object) { + if (object instanceof Token) { + Token anotherToken = (Token) object; + return anotherToken.line == line && anotherToken.column == column && anotherToken.value.equals(value); + } + return false; + } + + @Override + public int hashCode() { + int h = hash; + if (h == 0) { + h = value.hashCode(); + h = 31 * h + line; + h = 31 * h + column; + hash = h; + } + return h; + } + + @Override + public String toString() { + return "'" + value + "'[" + line + "," + column + "]"; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenChannel.java b/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenChannel.java new file mode 100644 index 00000000000..11e93b326cf --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenChannel.java @@ -0,0 +1,59 @@ +/* + * 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.token; + +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +import org.sonar.channel.Channel; +import org.sonar.channel.CodeBuffer.Cursor; +import org.sonar.channel.CodeReader; + +class TokenChannel extends Channel<TokenQueue> { + + private final StringBuilder tmpBuilder = new StringBuilder(); + private final Matcher matcher; + private String normalizationValue; + + public TokenChannel(String regex) { + matcher = Pattern.compile(regex).matcher(""); + } + + public TokenChannel(String regex, String normalizationValue) { + this(regex); + this.normalizationValue = normalizationValue; + } + + @Override + public boolean consume(CodeReader code, TokenQueue output) { + if (code.popTo(matcher, tmpBuilder) > 0) { + Cursor previousCursor = code.getPreviousCursor(); // see SONAR-2499 + if (normalizationValue != null) { + output.add(new Token(normalizationValue, previousCursor.getLine(), previousCursor.getColumn())); + } else { + output.add(new Token(tmpBuilder.toString(), previousCursor.getLine(), previousCursor.getColumn())); + } + tmpBuilder.setLength(0); // Godin: note that other channels use method delete in order to do the same thing + return true; + } + return false; + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenChunker.java b/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenChunker.java new file mode 100644 index 00000000000..bb9f5d3cf98 --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenChunker.java @@ -0,0 +1,141 @@ +/* + * 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.token; + +import java.io.File; +import java.io.FileInputStream; +import java.io.InputStreamReader; +import java.io.Reader; +import java.io.StringReader; +import java.nio.charset.Charset; +import java.util.ArrayList; +import java.util.List; + +import org.apache.commons.io.IOUtils; +import org.sonar.channel.Channel; +import org.sonar.channel.ChannelDispatcher; +import org.sonar.channel.CodeReader; +import org.sonar.channel.CodeReaderConfiguration; +import org.sonar.duplications.DuplicationsException; + +public final class TokenChunker { + + /** + * Some files can have large tokens (e.g. javadocs), so large buffer required. + * + * @see CodeReaderConfiguration#DEFAULT_BUFFER_CAPACITY + */ + private final static int BUFFER_CAPACITY = 80000; + + private final Charset charset; + private final ChannelDispatcher<TokenQueue> channelDispatcher; + + public static Builder builder() { + return new Builder(); + } + + private TokenChunker(Builder builder) { + this.charset = builder.charset; + this.channelDispatcher = builder.getChannelDispatcher(); + } + + public TokenQueue chunk(String sourceCode) { + return chunk(new StringReader(sourceCode)); + } + + public TokenQueue chunk(File file) { + InputStreamReader reader = null; + try { + reader = new InputStreamReader(new FileInputStream(file), charset); + return chunk(reader); + } catch (Exception e) { + throw new DuplicationsException("Unable to lex file : " + file.getAbsolutePath(), e); + } finally { + IOUtils.closeQuietly(reader); + } + } + + public TokenQueue chunk(Reader reader) { + CodeReaderConfiguration codeReaderConfiguration = new CodeReaderConfiguration(); + codeReaderConfiguration.setBufferCapacity(BUFFER_CAPACITY); + CodeReader code = new CodeReader(reader, codeReaderConfiguration); + TokenQueue queue = new TokenQueue(); + try { + channelDispatcher.consume(code, queue); + return queue; + } catch (Exception e) { + throw new DuplicationsException("Unable to lex source code at line : " + code.getLinePosition() + " and column : " + + code.getColumnPosition(), e); + } + } + + /** + * Note that order is important, e.g. + * <code>token("A").ignore("A")</code> for the input string "A" will produce token, whereas + * <code>ignore("A").token("A")</code> will not. + */ + public static final class Builder { + + private List<Channel> channels = new ArrayList<Channel>(); + private Charset charset = Charset.defaultCharset(); + + private Builder() { + } + + public TokenChunker build() { + return new TokenChunker(this); + } + + /** + * Defines that sequence of characters must be ignored, if it matches specified regular expression. + */ + public Builder ignore(String regularExpression) { + channels.add(new BlackHoleTokenChannel(regularExpression)); + return this; + } + + /** + * Defines that sequence of characters, which is matched specified regular expression, is a token. + */ + public Builder token(String regularExpression) { + channels.add(new TokenChannel(regularExpression)); + return this; + } + + /** + * Defines that sequence of characters, which is matched specified regular expression, is a token with specified value. + */ + public Builder token(String regularExpression, String normalizationValue) { + channels.add(new TokenChannel(regularExpression, normalizationValue)); + return this; + } + + private ChannelDispatcher<TokenQueue> getChannelDispatcher() { + return new ChannelDispatcher<TokenQueue>(channels); + } + + public Builder setCharset(Charset charset) { + this.charset = charset; + return this; + } + + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenQueue.java b/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenQueue.java new file mode 100644 index 00000000000..6fcd544e27e --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/token/TokenQueue.java @@ -0,0 +1,85 @@ +/* + * 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.token; + +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.ListIterator; + +public class TokenQueue implements Iterable<Token> { + + private final LinkedList<Token> tokenQueue; + + public TokenQueue(List<Token> tokenList) { + tokenQueue = new LinkedList<Token>(tokenList); + } + + public TokenQueue() { + tokenQueue = new LinkedList<Token>(); + } + + /** + * Retrieves, but does not remove, token from this queue. + * + * @return token from this queue, or <tt>null</tt> if this queue is empty. + */ + public Token peek() { + return tokenQueue.peek(); + } + + /** + * Retrieves and removes token from this queue. + * + * @return token from this queue, or <tt>null</tt> if this queue is empty. + */ + public Token poll() { + return tokenQueue.poll(); + } + + public int size() { + return tokenQueue.size(); + } + + public void add(Token token) { + tokenQueue.addLast(token); + } + + public boolean isNextTokenValue(String expectedValue) { + Token nextToken = tokenQueue.peek(); + if (nextToken == null) { + // queue is empty + return false; + } + return nextToken.getValue().equals(expectedValue); + } + + public Iterator<Token> iterator() { + return tokenQueue.iterator(); + } + + public void pushForward(List<Token> matchedTokenList) { + ListIterator<Token> iter = matchedTokenList.listIterator(matchedTokenList.size()); + while (iter.hasPrevious()) { + tokenQueue.addFirst(iter.previous()); + } + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/token/package-info.java b/sonar-duplications/src/main/java/org/sonar/duplications/token/package-info.java new file mode 100644 index 00000000000..a34f69058bc --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/token/package-info.java @@ -0,0 +1,27 @@ +/* + * 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 + */ + +/** + * Provides a basic framework to sequentially read any kind of character stream and create list of tokens. + * + * The entry point of this framework is the {@link org.sonar.duplications.token.TokenChunker} class. + */ +package org.sonar.duplications.token; + diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/utils/FastStringComparator.java b/sonar-duplications/src/main/java/org/sonar/duplications/utils/FastStringComparator.java new file mode 100644 index 00000000000..319f26faf3e --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/utils/FastStringComparator.java @@ -0,0 +1,57 @@ +/* + * 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.utils; + +import java.util.Comparator; + +/** + * More efficient (in terms of performance) implementation of a String comparator. + * Speed is gained by using hash code as a primary comparison attribute, which is cached for String. + * Be aware that this ordering is not lexicographic, however stable. + */ +public final class FastStringComparator implements Comparator<String> { + + public static final FastStringComparator INSTANCE = new FastStringComparator(); + + /** + * Compares two strings (not lexicographically). + */ + public int compare(String s1, String s2) { + if (s1 == s2) { // NOSONAR false-positive: Compare Objects With Equals + return 0; + } + int h1 = s1.hashCode(); + int h2 = s2.hashCode(); + if (h1 < h2) { + return -1; + } else if (h1 > h2) { + return 1; + } else { + return s1.compareTo(s2); + } + } + + /** + * Enforce use of a singleton instance. + */ + private FastStringComparator() { + } + +} diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/utils/SortedListsUtils.java b/sonar-duplications/src/main/java/org/sonar/duplications/utils/SortedListsUtils.java new file mode 100644 index 00000000000..39b482e61ae --- /dev/null +++ b/sonar-duplications/src/main/java/org/sonar/duplications/utils/SortedListsUtils.java @@ -0,0 +1,62 @@ +/* + * 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.utils; + +import java.util.Comparator; +import java.util.List; + +/** + * Provides utility methods for sorted lists. + */ +public final class SortedListsUtils { + + /** + * Returns true if all elements from second list also presented in first list. + * Both lists must be sorted. + * And both must implement {@link java.util.RandomAccess}, otherwise this method is inefficient in terms of performance. + * Running time - O(|container| + |list|). + */ + public static <T> boolean contains(List<T> container, List<T> list, Comparator<T> comparator) { + int j = 0; + for (int i = 0; i < list.size(); i++) { + T e1 = list.get(i); + boolean found = false; + for (; j < container.size(); j++) { + T e2 = container.get(j); + int c = comparator.compare(e1, e2); + if (c == 0) { + found = true; + break; + } else if (c < 0) { + // e1 is less than e2 - stop search, because all next elements e2 would be greater than e1 + return false; + } + } + if (!found) { + return false; + } + } + return true; + } + + private SortedListsUtils() { + } + +} diff --git a/sonar-duplications/src/test/files/java/MessageResources.java b/sonar-duplications/src/test/files/java/MessageResources.java new file mode 100644 index 00000000000..fbed9f7e738 --- /dev/null +++ b/sonar-duplications/src/test/files/java/MessageResources.java @@ -0,0 +1,508 @@ +/* + * $Id: MessageResources.java 471754 2006-11-06 14:55:09Z husted $ + * + * 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.struts.util; + +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; + +import java.io.Serializable; +import java.text.MessageFormat; +import java.util.HashMap; +import java.util.Locale; + +/** + * General purpose abstract class that describes an API for retrieving + * Locale-sensitive messages from underlying resource locations of an + * unspecified design, and optionally utilizing the <code>MessageFormat</code> + * class to produce internationalized messages with parametric replacement. + * <p> Calls to <code>getMessage()</code> variants without a + * <code>Locale</code> argument are presumed to be requesting a message string + * in the default <code>Locale</code> for this JVM. <p> Calls to + * <code>getMessage()</code> with an unknown key, or an unknown + * <code>Locale</code> will return <code>null</code> if the + * <code>returnNull</code> property is set to <code>true</code>. Otherwise, a + * suitable error message will be returned instead. <p> <strong>IMPLEMENTATION + * NOTE</strong> - Classes that extend this class must be Serializable so that + * instances may be used in distributable application server environments. + * + * @version $Rev: 471754 $ $Date: 2005-08-29 23:57:50 -0400 (Mon, 29 Aug 2005) + * $ + */ +public abstract class MessageResources implements Serializable { + // ------------------------------------------------------------- Properties + + /** + * Commons Logging instance. + */ + protected static Log log = LogFactory.getLog(MessageResources.class); + + // --------------------------------------------------------- Static Methods + + /** + * The default MessageResourcesFactory used to create MessageResources + * instances. + */ + protected static MessageResourcesFactory defaultFactory = null; + + /** + * The configuration parameter used to initialize this MessageResources. + */ + protected String config = null; + + /** + * The default Locale for our environment. + */ + protected Locale defaultLocale = Locale.getDefault(); + + /** + * The <code>MessageResourcesFactory</code> that created this instance. + */ + protected MessageResourcesFactory factory = null; + + /** + * The set of previously created MessageFormat objects, keyed by the key + * computed in <code>messageKey()</code>. + */ + protected HashMap formats = new HashMap(); + + /** + * Indicate is a <code>null</code> is returned instead of an error message + * string when an unknown Locale or key is requested. + */ + protected boolean returnNull = false; + + /** + * Indicates whether 'escape processing' should be performed on the error + * message string. + */ + private boolean escape = true; + + // ----------------------------------------------------------- Constructors + + /** + * Construct a new MessageResources according to the specified + * parameters. + * + * @param factory The MessageResourcesFactory that created us + * @param config The configuration parameter for this MessageResources + */ + public MessageResources(MessageResourcesFactory factory, String config) { + this(factory, config, false); + } + + /** + * Construct a new MessageResources according to the specified + * parameters. + * + * @param factory The MessageResourcesFactory that created us + * @param config The configuration parameter for this + * MessageResources + * @param returnNull The returnNull property we should initialize with + */ + public MessageResources(MessageResourcesFactory factory, String config, + boolean returnNull) { + super(); + this.factory = factory; + this.config = config; + this.returnNull = returnNull; + } + + /** + * The configuration parameter used to initialize this MessageResources. + * + * @return parameter used to initialize this MessageResources + */ + public String getConfig() { + return (this.config); + } + + /** + * The <code>MessageResourcesFactory</code> that created this instance. + * + * @return <code>MessageResourcesFactory</code> that created instance + */ + public MessageResourcesFactory getFactory() { + return (this.factory); + } + + /** + * Indicates that a <code>null</code> is returned instead of an error + * message string if an unknown Locale or key is requested. + * + * @return true if null is returned if unknown key or locale is requested + */ + public boolean getReturnNull() { + return (this.returnNull); + } + + /** + * Indicates that a <code>null</code> is returned instead of an error + * message string if an unknown Locale or key is requested. + * + * @param returnNull true Indicates that a <code>null</code> is returned + * if an unknown Locale or key is requested. + */ + public void setReturnNull(boolean returnNull) { + this.returnNull = returnNull; + } + + /** + * Indicates whether 'escape processing' should be performed on the error + * message string. + * + * @since Struts 1.2.8 + */ + public boolean isEscape() { + return escape; + } + + /** + * Set whether 'escape processing' should be performed on the error + * message string. + * + * @since Struts 1.2.8 + */ + public void setEscape(boolean escape) { + this.escape = escape; + } + + // --------------------------------------------------------- Public Methods + + /** + * Returns a text message for the specified key, for the default Locale. + * + * @param key The message key to look up + */ + public String getMessage(String key) { + return this.getMessage((Locale) null, key, null); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. + * + * @param key The message key to look up + * @param args An array of replacement parameters for placeholders + */ + public String getMessage(String key, Object[] args) { + return this.getMessage((Locale) null, key, args); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. + * + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + */ + public String getMessage(String key, Object arg0) { + return this.getMessage((Locale) null, key, arg0); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. + * + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + * @param arg1 The replacement for placeholder {1} in the message + */ + public String getMessage(String key, Object arg0, Object arg1) { + return this.getMessage((Locale) null, key, arg0, arg1); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. + * + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + * @param arg1 The replacement for placeholder {1} in the message + * @param arg2 The replacement for placeholder {2} in the message + */ + public String getMessage(String key, Object arg0, Object arg1, Object arg2) { + return this.getMessage((Locale) null, key, arg0, arg1, arg2); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. + * + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + * @param arg1 The replacement for placeholder {1} in the message + * @param arg2 The replacement for placeholder {2} in the message + * @param arg3 The replacement for placeholder {3} in the message + */ + public String getMessage(String key, Object arg0, Object arg1, Object arg2, + Object arg3) { + return this.getMessage((Locale) null, key, arg0, arg1, arg2, arg3); + } + + /** + * Returns a text message for the specified key, for the default Locale. A + * null string result will be returned by this method if no relevant + * message resource is found for this key or Locale, if the + * <code>returnNull</code> property is set. Otherwise, an appropriate + * error message will be returned. <p> This method must be implemented by + * a concrete subclass. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + */ + public abstract String getMessage(Locale locale, String key); + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. A null string result will be returned by this + * method if no resource bundle has been configured. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + * @param args An array of replacement parameters for placeholders + */ + public String getMessage(Locale locale, String key, Object[] args) { + // Cache MessageFormat instances as they are accessed + if (locale == null) { + locale = defaultLocale; + } + + MessageFormat format = null; + String formatKey = messageKey(locale, key); + + synchronized (formats) { + format = (MessageFormat) formats.get(formatKey); + + if (format == null) { + String formatString = getMessage(locale, key); + + if (formatString == null) { + return returnNull ? null : ("???" + formatKey + "???"); + } + + format = new MessageFormat(escape(formatString)); + format.setLocale(locale); + formats.put(formatKey, format); + } + } + + return format.format(args); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. A null string result will never be returned by + * this method. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + */ + public String getMessage(Locale locale, String key, Object arg0) { + return this.getMessage(locale, key, new Object[]{arg0}); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. A null string result will never be returned by + * this method. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + * @param arg1 The replacement for placeholder {1} in the message + */ + public String getMessage(Locale locale, String key, Object arg0, Object arg1) { + return this.getMessage(locale, key, new Object[]{arg0, arg1}); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. A null string result will never be returned by + * this method. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + * @param arg1 The replacement for placeholder {1} in the message + * @param arg2 The replacement for placeholder {2} in the message + */ + public String getMessage(Locale locale, String key, Object arg0, + Object arg1, Object arg2) { + return this.getMessage(locale, key, new Object[]{arg0, arg1, arg2}); + } + + /** + * Returns a text message after parametric replacement of the specified + * parameter placeholders. A null string result will never be returned by + * this method. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + * @param arg0 The replacement for placeholder {0} in the message + * @param arg1 The replacement for placeholder {1} in the message + * @param arg2 The replacement for placeholder {2} in the message + * @param arg3 The replacement for placeholder {3} in the message + */ + public String getMessage(Locale locale, String key, Object arg0, + Object arg1, Object arg2, Object arg3) { + return this.getMessage(locale, key, + new Object[]{arg0, arg1, arg2, arg3}); + } + + /** + * Return <code>true</code> if there is a defined message for the + * specified key in the system default locale. + * + * @param key The message key to look up + */ + public boolean isPresent(String key) { + return this.isPresent(null, key); + } + + /** + * Return <code>true</code> if there is a defined message for the + * specified key in the specified Locale. + * + * @param locale The requested message Locale, or <code>null</code> for + * the system default Locale + * @param key The message key to look up + */ + public boolean isPresent(Locale locale, String key) { + String message = getMessage(locale, key); + + if (message == null) { + return false; + } else if (message.startsWith("???") && message.endsWith("???")) { + return false; // FIXME - Only valid for default implementation + } else { + return true; + } + } + + // ------------------------------------------------------ Protected Methods + + /** + * Escape any single quote characters that are included in the specified + * message string. + * + * @param string The string to be escaped + */ + protected String escape(String string) { + if (!isEscape()) { + return string; + } + + if ((string == null) || (string.indexOf('\'') < 0)) { + return string; + } + + int n = string.length(); + StringBuffer sb = new StringBuffer(n); + + for (int i = 0; i < n; i++) { + char ch = string.charAt(i); + + if (ch == '\'') { + sb.append('\''); + } + + sb.append(ch); + } + + return sb.toString(); + } + + /** + * Compute and return a key to be used in caching information by a Locale. + * <strong>NOTE</strong> - The locale key for the default Locale in our + * environment is a zero length String. + * + * @param locale The locale for which a key is desired + */ + protected String localeKey(Locale locale) { + return (locale == null) ? "" : locale.toString(); + } + + /** + * Compute and return a key to be used in caching information by Locale + * and message key. + * + * @param locale The Locale for which this format key is calculated + * @param key The message key for which this format key is calculated + */ + protected String messageKey(Locale locale, String key) { + return (localeKey(locale) + "." + key); + } + + /** + * Compute and return a key to be used in caching information by locale + * key and message key. + * + * @param localeKey The locale key for which this cache key is calculated + * @param key The message key for which this cache key is + * calculated + */ + protected String messageKey(String localeKey, String key) { + return (localeKey + "." + key); + } + + /** + * Create and return an instance of <code>MessageResources</code> for the + * created by the default <code>MessageResourcesFactory</code>. + * + * @param config Configuration parameter for this message bundle. + */ + public synchronized static MessageResources getMessageResources( + String config) { + if (defaultFactory == null) { + defaultFactory = MessageResourcesFactory.createFactory(); + } + + return defaultFactory.createResources(config); + } + + /** + * Log a message to the Writer that has been configured for our use. + * + * @param message The message to be logged + */ + public void log(String message) { + log.debug(message); + } + + /** + * Log a message and exception to the Writer that has been configured for + * our use. + * + * @param message The message to be logged + * @param throwable The exception to be logged + */ + public void log(String message, Throwable throwable) { + log.debug(message, throwable); + } +} diff --git a/sonar-duplications/src/test/files/java/RequestUtils.java b/sonar-duplications/src/test/files/java/RequestUtils.java new file mode 100644 index 00000000000..2591a0d190a --- /dev/null +++ b/sonar-duplications/src/test/files/java/RequestUtils.java @@ -0,0 +1,1161 @@ +/* + * $Id: RequestUtils.java 727180 2008-12-16 21:54:10Z niallp $ + * + * 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.struts.util; + +import org.apache.commons.beanutils.BeanUtils; +import org.apache.commons.beanutils.PropertyUtils; +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; +import org.apache.struts.Globals; +import org.apache.struts.action.*; +import org.apache.struts.config.ActionConfig; +import org.apache.struts.config.FormBeanConfig; +import org.apache.struts.config.ForwardConfig; +import org.apache.struts.config.ModuleConfig; +import org.apache.struts.upload.FormFile; +import org.apache.struts.upload.MultipartRequestHandler; +import org.apache.struts.upload.MultipartRequestWrapper; + +import javax.servlet.ServletContext; +import javax.servlet.ServletException; +import javax.servlet.http.HttpServletRequest; +import javax.servlet.http.HttpSession; +import java.lang.reflect.InvocationTargetException; +import java.net.MalformedURLException; +import java.net.URL; +import java.util.*; + +/** + * <p>General purpose utility methods related to processing a servlet request + * in the Struts controller framework.</p> + * + * @version $Rev: 727180 $ $Date: 2008-12-17 00:54:10 +0300 (Ср., 17 дек. 2008) $ + */ +public class RequestUtils { + // ------------------------------------------------------- Static Variables + + /** + * <p>Commons Logging instance.</p> + */ + protected static Log log = LogFactory.getLog(RequestUtils.class); + + // --------------------------------------------------------- Public Methods + + /** + * <p>Create and return an absolute URL for the specified context-relative + * path, based on the server and context information in the specified + * request.</p> + * + * @param request The servlet request we are processing + * @param path The context-relative path (must start with '/') + * @return absolute URL based on context-relative path + * @throws MalformedURLException if we cannot create an absolute URL + */ + public static URL absoluteURL(HttpServletRequest request, String path) + throws MalformedURLException { + return (new URL(serverURL(request), request.getContextPath() + path)); + } + + /** + * <p>Return the <code>Class</code> object for the specified fully + * qualified class name, from this web application's class loader.</p> + * + * @param className Fully qualified class name to be loaded + * @return Class object + * @throws ClassNotFoundException if the class cannot be found + */ + public static Class applicationClass(String className) + throws ClassNotFoundException { + return applicationClass(className, null); + } + + /** + * <p>Return the <code>Class</code> object for the specified fully + * qualified class name, from this web application's class loader.</p> + * + * @param className Fully qualified class name to be loaded + * @param classLoader The desired classloader to use + * @return Class object + * @throws ClassNotFoundException if the class cannot be found + */ + public static Class applicationClass(String className, + ClassLoader classLoader) + throws ClassNotFoundException { + if (classLoader == null) { + // Look up the class loader to be used + classLoader = Thread.currentThread().getContextClassLoader(); + + if (classLoader == null) { + classLoader = RequestUtils.class.getClassLoader(); + } + } + + // Attempt to load the specified class + return (classLoader.loadClass(className)); + } + + /** + * <p>Return a new instance of the specified fully qualified class name, + * after loading the class from this web application's class loader. The + * specified class <strong>MUST</strong> have a public zero-arguments + * constructor.</p> + * + * @param className Fully qualified class name to use + * @return new instance of class + * @throws ClassNotFoundException if the class cannot be found + * @throws IllegalAccessException if the class or its constructor is not + * accessible + * @throws InstantiationException if this class represents an abstract + * class, an interface, an array class, a + * primitive type, or void + * @throws InstantiationException if this class has no zero-arguments + * constructor + */ + public static Object applicationInstance(String className) + throws ClassNotFoundException, IllegalAccessException, + InstantiationException { + return applicationInstance(className, null); + } + + /** + * <p>Return a new instance of the specified fully qualified class name, + * after loading the class from this web application's class loader. The + * specified class <strong>MUST</strong> have a public zero-arguments + * constructor.</p> + * + * @param className Fully qualified class name to use + * @param classLoader The desired classloader to use + * @return new instance of class + * @throws ClassNotFoundException if the class cannot be found + * @throws IllegalAccessException if the class or its constructor is not + * accessible + * @throws InstantiationException if this class represents an abstract + * class, an interface, an array class, a + * primitive type, or void + * @throws InstantiationException if this class has no zero-arguments + * constructor + */ + public static Object applicationInstance(String className, + ClassLoader classLoader) + throws ClassNotFoundException, IllegalAccessException, + InstantiationException { + return (applicationClass(className, classLoader).newInstance()); + } + + /** + * <p>Create (if necessary) and return an <code>ActionForm</code> instance + * appropriate for this request. If no <code>ActionForm</code> instance + * is required, return <code>null</code>.</p> + * + * @param request The servlet request we are processing + * @param mapping The action mapping for this request + * @param moduleConfig The configuration for this module + * @param servlet The action servlet + * @return ActionForm instance associated with this request + */ + public static ActionForm createActionForm(HttpServletRequest request, + ActionMapping mapping, ModuleConfig moduleConfig, ActionServlet servlet) { + // Is there a form bean associated with this mapping? + String attribute = mapping.getAttribute(); + + if (attribute == null) { + return (null); + } + + // Look up the form bean configuration information to use + String name = mapping.getName(); + FormBeanConfig config = moduleConfig.findFormBeanConfig(name); + + if (config == null) { + log.warn("No FormBeanConfig found under '" + name + "'"); + + return (null); + } + + ActionForm instance = + lookupActionForm(request, attribute, mapping.getScope()); + + // Can we recycle the existing form bean instance (if there is one)? + if ((instance != null) && config.canReuse(instance)) { + return (instance); + } + + return createActionForm(config, servlet); + } + + private static ActionForm lookupActionForm(HttpServletRequest request, + String attribute, String scope) { + // Look up any existing form bean instance + if (log.isDebugEnabled()) { + log.debug(" Looking for ActionForm bean instance in scope '" + + scope + "' under attribute key '" + attribute + "'"); + } + + ActionForm instance = null; + HttpSession session = null; + + if ("request".equals(scope)) { + instance = (ActionForm) request.getAttribute(attribute); + } else { + session = request.getSession(); + instance = (ActionForm) session.getAttribute(attribute); + } + + return (instance); + } + + /** + * <p>Create and return an <code>ActionForm</code> instance appropriate to + * the information in <code>config</code>.</p> + * <p/> + * <p>Does not perform any checks to see if an existing ActionForm exists + * which could be reused.</p> + * + * @param config The configuration for the Form bean which is to be + * created. + * @param servlet The action servlet + * @return ActionForm instance associated with this request + */ + public static ActionForm createActionForm(FormBeanConfig config, + ActionServlet servlet) { + if (config == null) { + return (null); + } + + ActionForm instance = null; + + // Create and return a new form bean instance + try { + instance = config.createActionForm(servlet); + + if (log.isDebugEnabled()) { + log.debug(" Creating new " + + (config.getDynamic() ? "DynaActionForm" : "ActionForm") + + " instance of type '" + config.getType() + "'"); + log.trace(" --> " + instance); + } + } catch (Throwable t) { + log.error(servlet.getInternal().getMessage("formBean", + config.getType()), t); + } + + return (instance); + } + + /** + * <p>Retrieves the servlet mapping pattern for the specified {@link ActionServlet}.</p> + * + * @return the servlet mapping + * @see Globals#SERVLET_KEY + * @since Struts 1.3.6 + */ + public static String getServletMapping(ActionServlet servlet) { + ServletContext servletContext = servlet.getServletConfig().getServletContext(); + return (String) servletContext.getAttribute(Globals.SERVLET_KEY); + } + + /** + * <p>Look up and return current user locale, based on the specified + * parameters.</p> + * + * @param request The request used to lookup the Locale + * @param locale Name of the session attribute for our user's Locale. If + * this is <code>null</code>, the default locale key is + * used for the lookup. + * @return current user locale + * @since Struts 1.2 + */ + public static Locale getUserLocale(HttpServletRequest request, String locale) { + Locale userLocale = null; + HttpSession session = request.getSession(false); + + if (locale == null) { + locale = Globals.LOCALE_KEY; + } + + // Only check session if sessions are enabled + if (session != null) { + userLocale = (Locale) session.getAttribute(locale); + } + + if (userLocale == null) { + // Returns Locale based on Accept-Language header or the server default + userLocale = request.getLocale(); + } + + return userLocale; + } + + /** + * <p>Populate the properties of the specified JavaBean from the specified + * HTTP request, based on matching each parameter name against the + * corresponding JavaBeans "property setter" methods in the bean's class. + * Suitable conversion is done for argument types as described under + * <code>convert()</code>.</p> + * + * @param bean The JavaBean whose properties are to be set + * @param request The HTTP request whose parameters are to be used to + * populate bean properties + * @throws ServletException if an exception is thrown while setting + * property values + */ + public static void populate(Object bean, HttpServletRequest request) + throws ServletException { + populate(bean, null, null, request); + } + + /** + * <p>Populate the properties of the specified JavaBean from the specified + * HTTP request, based on matching each parameter name (plus an optional + * prefix and/or suffix) against the corresponding JavaBeans "property + * setter" methods in the bean's class. Suitable conversion is done for + * argument types as described under <code>setProperties</code>.</p> + * <p/> + * <p>If you specify a non-null <code>prefix</code> and a non-null + * <code>suffix</code>, the parameter name must match + * <strong>both</strong> conditions for its value(s) to be used in + * populating bean properties. If the request's content type is + * "multipart/form-data" and the method is "POST", the + * <code>HttpServletRequest</code> object will be wrapped in a + * <code>MultipartRequestWrapper</code object.</p> + * + * @param bean The JavaBean whose properties are to be set + * @param prefix The prefix (if any) to be prepend to bean property names + * when looking for matching parameters + * @param suffix The suffix (if any) to be appended to bean property + * names when looking for matching parameters + * @param request The HTTP request whose parameters are to be used to + * populate bean properties + * @throws ServletException if an exception is thrown while setting + * property values + */ + public static void populate(Object bean, String prefix, String suffix, + HttpServletRequest request) + throws ServletException { + // Build a list of relevant request parameters from this request + HashMap properties = new HashMap(); + + // Iterator of parameter names + Enumeration names = null; + + // Map for multipart parameters + Map multipartParameters = null; + + String contentType = request.getContentType(); + String method = request.getMethod(); + boolean isMultipart = false; + + if (bean instanceof ActionForm) { + ((ActionForm) bean).setMultipartRequestHandler(null); + } + + MultipartRequestHandler multipartHandler = null; + if ((contentType != null) + && (contentType.startsWith("multipart/form-data")) + && (method.equalsIgnoreCase("POST"))) { + // Get the ActionServletWrapper from the form bean + ActionServletWrapper servlet; + + if (bean instanceof ActionForm) { + servlet = ((ActionForm) bean).getServletWrapper(); + } else { + throw new ServletException("bean that's supposed to be " + + "populated from a multipart request is not of type " + + "\"org.apache.struts.action.ActionForm\", but type " + + "\"" + bean.getClass().getName() + "\""); + } + + // Obtain a MultipartRequestHandler + multipartHandler = getMultipartHandler(request); + + if (multipartHandler != null) { + isMultipart = true; + + // Set servlet and mapping info + servlet.setServletFor(multipartHandler); + multipartHandler.setMapping((ActionMapping) request + .getAttribute(Globals.MAPPING_KEY)); + + // Initialize multipart request class handler + multipartHandler.handleRequest(request); + + //stop here if the maximum length has been exceeded + Boolean maxLengthExceeded = + (Boolean) request.getAttribute(MultipartRequestHandler.ATTRIBUTE_MAX_LENGTH_EXCEEDED); + + if ((maxLengthExceeded != null) + && (maxLengthExceeded.booleanValue())) { + ((ActionForm) bean).setMultipartRequestHandler(multipartHandler); + return; + } + + //retrieve form values and put into properties + multipartParameters = + getAllParametersForMultipartRequest(request, + multipartHandler); + names = Collections.enumeration(multipartParameters.keySet()); + } + } + + if (!isMultipart) { + names = request.getParameterNames(); + } + + while (names.hasMoreElements()) { + String name = (String) names.nextElement(); + String stripped = name; + + if (prefix != null) { + if (!stripped.startsWith(prefix)) { + continue; + } + + stripped = stripped.substring(prefix.length()); + } + + if (suffix != null) { + if (!stripped.endsWith(suffix)) { + continue; + } + + stripped = + stripped.substring(0, stripped.length() - suffix.length()); + } + + Object parameterValue = null; + + if (isMultipart) { + parameterValue = multipartParameters.get(name); + parameterValue = rationalizeMultipleFileProperty(bean, name, parameterValue); + } else { + parameterValue = request.getParameterValues(name); + } + + // Populate parameters, except "standard" struts attributes + // such as 'org.apache.struts.action.CANCEL' + if (!(stripped.startsWith("org.apache.struts."))) { + properties.put(stripped, parameterValue); + } + } + + // Set the corresponding properties of our bean + try { + BeanUtils.populate(bean, properties); + } catch (Exception e) { + throw new ServletException("BeanUtils.populate", e); + } finally { + if (multipartHandler != null) { + // Set the multipart request handler for our ActionForm. + // If the bean isn't an ActionForm, an exception would have been + // thrown earlier, so it's safe to assume that our bean is + // in fact an ActionForm. + ((ActionForm) bean).setMultipartRequestHandler(multipartHandler); + } + } + } + + /** + * <p>Populates the parameters of the specified ActionRedirect from + * the specified HTTP request.</p> + * + * @param redirect The ActionRedirect whose parameters are to be set + * @param request The HTTP request whose parameters are to be used + * @since Struts 1.4 + */ + public static void populate(ActionRedirect redirect, HttpServletRequest request) { + assert (redirect != null) : "redirect is required"; + assert (request != null) : "request is required"; + + Enumeration e = request.getParameterNames(); + while (e.hasMoreElements()) { + String name = (String) e.nextElement(); + String[] values = request.getParameterValues(name); + redirect.addParameter(name, values); + } + } + + /** + * <p>If the given form bean can accept multiple FormFile objects but the user only uploaded a single, then + * the property will not match the form bean type. This method performs some simple checks to try to accommodate + * that situation.</p> + * + * @param bean + * @param name + * @param parameterValue + * @return + * @throws ServletException if the introspection has any errors. + */ + private static Object rationalizeMultipleFileProperty(Object bean, String name, Object parameterValue) throws ServletException { + if (!(parameterValue instanceof FormFile)) { + return parameterValue; + } + + FormFile formFileValue = (FormFile) parameterValue; + try { + Class propertyType = PropertyUtils.getPropertyType(bean, name); + + if (propertyType == null) { + return parameterValue; + } + + if (List.class.isAssignableFrom(propertyType)) { + ArrayList list = new ArrayList(1); + list.add(formFileValue); + return list; + } + + if (propertyType.isArray() && propertyType.getComponentType().equals(FormFile.class)) { + return new FormFile[]{formFileValue}; + } + + } catch (IllegalAccessException e) { + throw new ServletException(e); + } catch (InvocationTargetException e) { + throw new ServletException(e); + } catch (NoSuchMethodException e) { + throw new ServletException(e); + } + + // no changes + return parameterValue; + + } + + /** + * <p>Try to locate a multipart request handler for this request. First, + * look for a mapping-specific handler stored for us under an attribute. + * If one is not present, use the global multipart handler, if there is + * one.</p> + * + * @param request The HTTP request for which the multipart handler should + * be found. + * @return the multipart handler to use, or null if none is found. + * @throws ServletException if any exception is thrown while attempting to + * locate the multipart handler. + */ + private static MultipartRequestHandler getMultipartHandler( + HttpServletRequest request) + throws ServletException { + MultipartRequestHandler multipartHandler = null; + String multipartClass = + (String) request.getAttribute(Globals.MULTIPART_KEY); + + request.removeAttribute(Globals.MULTIPART_KEY); + + // Try to initialize the mapping specific request handler + if (multipartClass != null) { + try { + multipartHandler = + (MultipartRequestHandler) applicationInstance(multipartClass); + } catch (ClassNotFoundException cnfe) { + log.error("MultipartRequestHandler class \"" + multipartClass + + "\" in mapping class not found, " + + "defaulting to global multipart class"); + } catch (InstantiationException ie) { + log.error("InstantiationException when instantiating " + + "MultipartRequestHandler \"" + multipartClass + "\", " + + "defaulting to global multipart class, exception: " + + ie.getMessage()); + } catch (IllegalAccessException iae) { + log.error("IllegalAccessException when instantiating " + + "MultipartRequestHandler \"" + multipartClass + "\", " + + "defaulting to global multipart class, exception: " + + iae.getMessage()); + } + + if (multipartHandler != null) { + return multipartHandler; + } + } + + ModuleConfig moduleConfig = + ModuleUtils.getInstance().getModuleConfig(request); + + multipartClass = moduleConfig.getControllerConfig().getMultipartClass(); + + // Try to initialize the global request handler + if (multipartClass != null) { + try { + multipartHandler = + (MultipartRequestHandler) applicationInstance(multipartClass); + } catch (ClassNotFoundException cnfe) { + throw new ServletException("Cannot find multipart class \"" + + multipartClass + "\"", cnfe); + } catch (InstantiationException ie) { + throw new ServletException( + "InstantiationException when instantiating " + + "multipart class \"" + multipartClass + "\"", ie); + } catch (IllegalAccessException iae) { + throw new ServletException( + "IllegalAccessException when instantiating " + + "multipart class \"" + multipartClass + "\"", iae); + } + + if (multipartHandler != null) { + return multipartHandler; + } + } + + return multipartHandler; + } + + /** + * <p>Create a <code>Map</code> containing all of the parameters supplied + * for a multipart request, keyed by parameter name. In addition to text + * and file elements from the multipart body, query string parameters are + * included as well.</p> + * + * @param request The (wrapped) HTTP request whose parameters are + * to be added to the map. + * @param multipartHandler The multipart handler used to parse the + * request. + * @return the map containing all parameters for this multipart request. + */ + private static Map getAllParametersForMultipartRequest( + HttpServletRequest request, MultipartRequestHandler multipartHandler) { + Map parameters = new HashMap(); + Hashtable elements = multipartHandler.getAllElements(); + Enumeration e = elements.keys(); + + while (e.hasMoreElements()) { + String key = (String) e.nextElement(); + + parameters.put(key, elements.get(key)); + } + + if (request instanceof MultipartRequestWrapper) { + request = + (HttpServletRequest) ((MultipartRequestWrapper) request) + .getRequest(); + e = request.getParameterNames(); + + while (e.hasMoreElements()) { + String key = (String) e.nextElement(); + + parameters.put(key, request.getParameterValues(key)); + } + } else { + log.debug("Gathering multipart parameters for unwrapped request"); + } + + return parameters; + } + + /** + * <p>Compute the printable representation of a URL, leaving off the + * scheme/host/port part if no host is specified. This will typically be + * the case for URLs that were originally created from relative or + * context-relative URIs.</p> + * + * @param url URL to render in a printable representation + * @return printable representation of a URL + */ + public static String printableURL(URL url) { + if (url.getHost() != null) { + return (url.toString()); + } + + String file = url.getFile(); + String ref = url.getRef(); + + if (ref == null) { + return (file); + } else { + StringBuffer sb = new StringBuffer(file); + + sb.append('#'); + sb.append(ref); + + return (sb.toString()); + } + } + + /** + * <p>Return the context-relative URL that corresponds to the specified + * {@link ActionConfig}, relative to the module associated with the + * current modules's {@link ModuleConfig}.</p> + * + * @param request The servlet request we are processing + * @param action ActionConfig to be evaluated + * @param pattern URL pattern used to map the controller servlet + * @return context-relative URL relative to the module + * @since Struts 1.1 + */ + public static String actionURL(HttpServletRequest request, + ActionConfig action, String pattern) { + StringBuffer sb = new StringBuffer(); + + if (pattern.endsWith("/*")) { + sb.append(pattern.substring(0, pattern.length() - 2)); + sb.append(action.getPath()); + } else if (pattern.startsWith("*.")) { + ModuleConfig appConfig = + ModuleUtils.getInstance().getModuleConfig(request); + + sb.append(appConfig.getPrefix()); + sb.append(action.getPath()); + sb.append(pattern.substring(1)); + } else { + throw new IllegalArgumentException(pattern); + } + + return sb.toString(); + } + + /** + * <p>Return the context-relative URL that corresponds to the specified + * <code>ForwardConfig</code>. The URL is calculated based on the + * properties of the {@link ForwardConfig} instance as follows:</p> + * <p/> + * <ul> + * <p/> + * <p/> + * <li>If the <code>contextRelative</code> property is set, it is assumed + * that the <code>path</code> property contains a path that is already + * context-relative: + * <p/> + * <ul> + * <p/> + * <li>If the <code>path</code> property value starts with a slash, it is + * returned unmodified.</li> <li>If the <code>path</code> property value + * does not start with a slash, a slash is prepended.</li> + * <p/> + * </ul></li> + * <p/> + * <li>Acquire the <code>forwardPattern</code> property from the + * <code>ControllerConfig</code> for the application module used to + * process this request. If no pattern was configured, default to a + * pattern of <code>$M$P</code>, which is compatible with the hard-coded + * mapping behavior in Struts 1.0.</li> + * <p/> + * <li>Process the acquired <code>forwardPattern</code>, performing the + * following substitutions: + * <p/> + * <ul> + * <p/> + * <li><strong>$M</strong> - Replaced by the module prefix for the + * application module processing this request.</li> + * <p/> + * <li><strong>$P</strong> - Replaced by the <code>path</code> property of + * the specified {@link ForwardConfig}, prepended with a slash if it does + * not start with one.</li> + * <p/> + * <li><strong>$$</strong> - Replaced by a single dollar sign + * character.</li> + * <p/> + * <li><strong>$x</strong> (where "x" is any charater not listed above) - + * Silently omit these two characters from the result value. (This has + * the side effect of causing all other $+letter combinations to be + * reserved.)</li> + * <p/> + * </ul></li> + * <p/> + * </ul> + * + * @param request The servlet request we are processing + * @param forward ForwardConfig to be evaluated + * @return context-relative URL + * @since Struts 1.1 + */ + public static String forwardURL(HttpServletRequest request, + ForwardConfig forward) { + return forwardURL(request, forward, null); + } + + /** + * <p>Return the context-relative URL that corresponds to the specified + * <code>ForwardConfig</code>. The URL is calculated based on the + * properties of the {@link ForwardConfig} instance as follows:</p> + * <p/> + * <ul> + * <p/> + * <li>If the <code>contextRelative</code> property is set, it is assumed + * that the <code>path</code> property contains a path that is already + * context-relative: <ul> + * <p/> + * <li>If the <code>path</code> property value starts with a slash, it is + * returned unmodified.</li> <li>If the <code>path</code> property value + * does not start with a slash, a slash is prepended.</li> + * <p/> + * </ul></li> + * <p/> + * <li>Acquire the <code>forwardPattern</code> property from the + * <code>ControllerConfig</code> for the application module used to + * process this request. If no pattern was configured, default to a + * pattern of <code>$M$P</code>, which is compatible with the hard-coded + * mapping behavior in Struts 1.0.</li> + * <p/> + * <li>Process the acquired <code>forwardPattern</code>, performing the + * following substitutions: <ul> <li><strong>$M</strong> - Replaced by the + * module prefix for the application module processing this request.</li> + * <p/> + * <li><strong>$P</strong> - Replaced by the <code>path</code> property of + * the specified {@link ForwardConfig}, prepended with a slash if it does + * not start with one.</li> + * <p/> + * <li><strong>$$</strong> - Replaced by a single dollar sign + * character.</li> + * <p/> + * <li><strong>$x</strong> (where "x" is any charater not listed above) - + * Silently omit these two characters from the result value. (This has + * the side effect of causing all other $+letter combinations to be + * reserved.)</li> + * <p/> + * </ul></li></ul> + * + * @param request The servlet request we are processing + * @param forward ForwardConfig to be evaluated + * @param moduleConfig Base forward on this module config. + * @return context-relative URL + * @since Struts 1.2 + */ + public static String forwardURL(HttpServletRequest request, + ForwardConfig forward, ModuleConfig moduleConfig) { + //load the current moduleConfig, if null + if (moduleConfig == null) { + moduleConfig = ModuleUtils.getInstance().getModuleConfig(request); + } + + String path = forward.getPath(); + + //load default prefix + String prefix = moduleConfig.getPrefix(); + + //override prefix if supplied by forward + if (forward.getModule() != null) { + prefix = forward.getModule(); + + if ("/".equals(prefix)) { + prefix = ""; + } + } + + StringBuffer sb = new StringBuffer(); + + // Calculate a context relative path for this ForwardConfig + String forwardPattern = + moduleConfig.getControllerConfig().getForwardPattern(); + + if (forwardPattern == null) { + // Performance optimization for previous default behavior + sb.append(prefix); + + // smoothly insert a '/' if needed + if (!path.startsWith("/")) { + sb.append("/"); + } + + sb.append(path); + } else { + boolean dollar = false; + + for (int i = 0; i < forwardPattern.length(); i++) { + char ch = forwardPattern.charAt(i); + + if (dollar) { + switch (ch) { + case 'M': + sb.append(prefix); + + break; + + case 'P': + + // add '/' if needed + if (!path.startsWith("/")) { + sb.append("/"); + } + + sb.append(path); + + break; + + case '$': + sb.append('$'); + + break; + + default: + ; // Silently swallow + } + + dollar = false; + + continue; + } else if (ch == '$') { + dollar = true; + } else { + sb.append(ch); + } + } + } + + return (sb.toString()); + } + + /** + * <p>Return the URL representing the current request. This is equivalent + * to <code>HttpServletRequest.getRequestURL</code> in Servlet 2.3.</p> + * + * @param request The servlet request we are processing + * @return URL representing the current request + * @throws MalformedURLException if a URL cannot be created + */ + public static URL requestURL(HttpServletRequest request) + throws MalformedURLException { + StringBuffer url = requestToServerUriStringBuffer(request); + + return (new URL(url.toString())); + } + + /** + * <p>Return the URL representing the scheme, server, and port number of + * the current request. Server-relative URLs can be created by simply + * appending the server-relative path (starting with '/') to this.</p> + * + * @param request The servlet request we are processing + * @return URL representing the scheme, server, and port number of the + * current request + * @throws MalformedURLException if a URL cannot be created + */ + public static URL serverURL(HttpServletRequest request) + throws MalformedURLException { + StringBuffer url = requestToServerStringBuffer(request); + + return (new URL(url.toString())); + } + + /** + * <p>Return the string representing the scheme, server, and port number + * of the current request. Server-relative URLs can be created by simply + * appending the server-relative path (starting with '/') to this.</p> + * + * @param request The servlet request we are processing + * @return URL representing the scheme, server, and port number of the + * current request + * @since Struts 1.2.0 + */ + public static StringBuffer requestToServerUriStringBuffer( + HttpServletRequest request) { + StringBuffer serverUri = + createServerUriStringBuffer(request.getScheme(), + request.getServerName(), request.getServerPort(), + request.getRequestURI()); + + return serverUri; + } + + /** + * <p>Return <code>StringBuffer</code> representing the scheme, server, + * and port number of the current request. Server-relative URLs can be + * created by simply appending the server-relative path (starting with + * '/') to this.</p> + * + * @param request The servlet request we are processing + * @return URL representing the scheme, server, and port number of the + * current request + * @since Struts 1.2.0 + */ + public static StringBuffer requestToServerStringBuffer( + HttpServletRequest request) { + return createServerStringBuffer(request.getScheme(), + request.getServerName(), request.getServerPort()); + } + + /** + * <p>Return <code>StringBuffer</code> representing the scheme, server, + * and port number of the current request.</p> + * + * @param scheme The scheme name to use + * @param server The server name to use + * @param port The port value to use + * @return StringBuffer in the form scheme: server: port + * @since Struts 1.2.0 + */ + public static StringBuffer createServerStringBuffer(String scheme, + String server, int port) { + StringBuffer url = new StringBuffer(); + + if (port < 0) { + port = 80; // Work around java.net.URL bug + } + + url.append(scheme); + url.append("://"); + url.append(server); + + if ((scheme.equals("http") && (port != 80)) + || (scheme.equals("https") && (port != 443))) { + url.append(':'); + url.append(port); + } + + return url; + } + + /** + * <p>Return <code>StringBuffer</code> representing the scheme, server, + * and port number of the current request.</p> + * + * @param scheme The scheme name to use + * @param server The server name to use + * @param port The port value to use + * @param uri The uri value to use + * @return StringBuffer in the form scheme: server: port + * @since Struts 1.2.0 + */ + public static StringBuffer createServerUriStringBuffer(String scheme, + String server, int port, String uri) { + StringBuffer serverUri = createServerStringBuffer(scheme, server, port); + + serverUri.append(uri); + + return serverUri; + } + + /** + * <p>Returns the true path of the destination action if the specified forward + * is an action-aliased URL. This method version forms the URL based on + * the current request; selecting the current module if the forward does not + * explicitly contain a module path.</p> + * + * @param forward the forward config + * @param request the current request + * @param servlet the servlet handling the current request + * @return the context-relative URL of the action if the forward has an action identifier; otherwise <code>null</code>. + * @since Struts 1.3.6 + */ + public static String actionIdURL(ForwardConfig forward, HttpServletRequest request, ActionServlet servlet) { + ModuleConfig moduleConfig = null; + if (forward.getModule() != null) { + String prefix = forward.getModule(); + moduleConfig = ModuleUtils.getInstance().getModuleConfig(prefix, servlet.getServletContext()); + } else { + moduleConfig = ModuleUtils.getInstance().getModuleConfig(request); + } + return actionIdURL(forward.getPath(), moduleConfig, servlet); + } + + /** + * <p>Returns the true path of the destination action if the specified forward + * is an action-aliased URL. This method version forms the URL based on + * the specified module. + * + * @param originalPath the action-aliased path + * @param moduleConfig the module config for this request + * @param servlet the servlet handling the current request + * @return the context-relative URL of the action if the path has an action identifier; otherwise <code>null</code>. + * @since Struts 1.3.6 + */ + public static String actionIdURL(String originalPath, ModuleConfig moduleConfig, ActionServlet servlet) { + if (originalPath.startsWith("http") || originalPath.startsWith("/")) { + return null; + } + + // Split the forward path into the resource and query string; + // it is possible a forward (or redirect) has added parameters. + String actionId = null; + String qs = null; + int qpos = originalPath.indexOf("?"); + if (qpos == -1) { + actionId = originalPath; + } else { + actionId = originalPath.substring(0, qpos); + qs = originalPath.substring(qpos); + } + + // Find the action of the given actionId + ActionConfig actionConfig = moduleConfig.findActionConfigId(actionId); + if (actionConfig == null) { + if (log.isDebugEnabled()) { + log.debug("No actionId found for " + actionId); + } + return null; + } + + String path = actionConfig.getPath(); + String mapping = RequestUtils.getServletMapping(servlet); + StringBuffer actionIdPath = new StringBuffer(); + + // Form the path based on the servlet mapping pattern + if (mapping.startsWith("*")) { + actionIdPath.append(path); + actionIdPath.append(mapping.substring(1)); + } else if (mapping.startsWith("/")) { // implied ends with a * + mapping = mapping.substring(0, mapping.length() - 1); + if (mapping.endsWith("/") && path.startsWith("/")) { + actionIdPath.append(mapping); + actionIdPath.append(path.substring(1)); + } else { + actionIdPath.append(mapping); + actionIdPath.append(path); + } + } else { + log.warn("Unknown servlet mapping pattern"); + actionIdPath.append(path); + } + + // Lastly add any query parameters (the ? is part of the query string) + if (qs != null) { + actionIdPath.append(qs); + } + + // Return the path + if (log.isDebugEnabled()) { + log.debug(originalPath + " unaliased to " + actionIdPath.toString()); + } + return actionIdPath.toString(); + } + + /** + * Determines whether the current request is forwarded. + * + * @param request current HTTP request + * @return true if the request is forwarded; otherwise false + * @since Struts 1.4 + */ + public static boolean isRequestForwarded(HttpServletRequest request) { + return (request.getAttribute("javax.servlet.forward.request_uri") != null); + } + + /** + * Determines whether the current request is included. + * + * @param request current HTTP request + * @return true if the request is included; otherwise false + * @since Struts 1.4 + */ + public static boolean isRequestIncluded(HttpServletRequest request) { + return (request.getAttribute("javax.servlet.include.request_uri") != null); + } + + /** + * Verifies whether current request is forwarded from one action to + * another or not. + * + * @param request current HTTP request + * @return true if the request is chained; otherwise false + * @since Struts 1.4 + */ + public static boolean isRequestChained(HttpServletRequest request) { + return (request.getAttribute(Globals.CHAIN_KEY) != null); + } +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/DuplicationsTestUtil.java b/sonar-duplications/src/test/java/org/sonar/duplications/DuplicationsTestUtil.java new file mode 100644 index 00000000000..c1a37bba1ae --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/DuplicationsTestUtil.java @@ -0,0 +1,32 @@ +/* + * 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; + +import java.io.File; + +public class DuplicationsTestUtil { + + public static final File fileDir = new File("src/test/files/"); + + public static File findFile(String relativePathToFile) { + return new File(fileDir, relativePathToFile); + } + +} 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 })); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/BlocksGroupTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/BlocksGroupTest.java new file mode 100644 index 00000000000..a8c44f67784 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/BlocksGroupTest.java @@ -0,0 +1,200 @@ +/* + * 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.detector.original; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +import org.junit.Test; +import org.sonar.duplications.block.Block; + +public class BlocksGroupTest { + + /** + * {@link BlocksGroup} uses only resourceId and index from block, thus we can simplify testing. + */ + private static Block newBlock(String resourceId, int indexInFile) { + return new Block(resourceId, null, indexInFile, indexInFile, indexInFile); + } + + public static BlocksGroup newBlocksGroup(Block... blocks) { + BlocksGroup result = BlocksGroup.empty(); + for (Block block : blocks) { + result.blocks.add(block); + } + return result; + } + + @Test + public void shouldReturnSize() { + BlocksGroup group = newBlocksGroup(newBlock("a", 1), newBlock("b", 2)); + assertThat(group.size(), is(2)); + } + + @Test + public void shouldCreateEmptyGroup() { + assertThat(BlocksGroup.empty().size(), is(0)); + } + + @Test + public void testSubsumedBy() { + BlocksGroup group1 = newBlocksGroup(newBlock("a", 1), newBlock("b", 2)); + BlocksGroup group2 = newBlocksGroup(newBlock("a", 2), newBlock("b", 3), newBlock("c", 4)); + // block "c" from group2 does not have corresponding block in group1 + assertThat(group2.subsumedBy(group1, 1), is(false)); + } + + @Test + public void testSubsumedBy2() { + BlocksGroup group1 = newBlocksGroup(newBlock("a", 1), newBlock("b", 2)); + BlocksGroup group2 = newBlocksGroup(newBlock("a", 2), newBlock("b", 3)); + BlocksGroup group3 = newBlocksGroup(newBlock("a", 3), newBlock("b", 4)); + BlocksGroup group4 = newBlocksGroup(newBlock("a", 4), newBlock("b", 5)); + + assertThat(group2.subsumedBy(group1, 1), is(true)); // correction of index - 1 + + assertThat(group3.subsumedBy(group1, 2), is(true)); // correction of index - 2 + assertThat(group3.subsumedBy(group2, 1), is(true)); // correction of index - 1 + + assertThat(group4.subsumedBy(group1, 3), is(true)); // correction of index - 3 + assertThat(group4.subsumedBy(group2, 2), is(true)); // correction of index - 2 + assertThat(group4.subsumedBy(group3, 1), is(true)); // correction of index - 1 + } + + @Test + public void testIntersect() { + BlocksGroup group1 = newBlocksGroup(newBlock("a", 1), newBlock("b", 2)); + BlocksGroup group2 = newBlocksGroup(newBlock("a", 2), newBlock("b", 3)); + BlocksGroup intersection = group1.intersect(group2); + assertThat(intersection.size(), is(2)); + } + + /** + * Results for this test taken from results of work of naive implementation. + */ + @Test + public void testSubsumedBy3() { + // ['a'[2|2-7]:3, 'b'[0|0-5]:3] subsumedBy ['a'[1|1-6]:2] false + assertThat(newBlocksGroup(newBlock("a", 2), newBlock("b", 0)) + .subsumedBy(newBlocksGroup(newBlock("a", 1)), 1), + is(false)); + + // ['a'[3|3-8]:4, 'b'[1|1-6]:4] subsumedBy ['a'[1|1-6]:2] false + assertThat(newBlocksGroup(newBlock("a", 3), newBlock("b", 1)) + .subsumedBy(newBlocksGroup(newBlock("a", 1)), 1), + is(false)); + + // ['a'[4|4-9]:5, 'b'[2|2-7]:5] subsumedBy ['a'[1|1-6]:2] false + assertThat(newBlocksGroup(newBlock("a", 4), newBlock("b", 2)) + .subsumedBy(newBlocksGroup(newBlock("a", 1)), 1), + is(false)); + + // ['a'[5|5-10]:6, 'b'[3|3-8]:6] subsumedBy ['a'[1|1-6]:2] false + assertThat(newBlocksGroup(newBlock("a", 5), newBlock("b", 3)) + .subsumedBy(newBlocksGroup(newBlock("a", 1)), 1), + is(false)); + + // ['a'[3|3-8]:4, 'b'[1|1-6]:4] subsumedBy ['a'[2|2-7]:3, 'b'[0|0-5]:3] true + assertThat(newBlocksGroup(newBlock("a", 3), newBlock("b", 1)) + .subsumedBy(newBlocksGroup(newBlock("a", 2), newBlock("b", 0)), 1), + is(true)); + + // ['a'[4|4-9]:5, 'b'[2|2-7]:5, 'c'[0|0-5]:5] subsumedBy ['a'[3|3-8]:4, 'b'[1|1-6]:4] false + assertThat(newBlocksGroup(newBlock("a", 4), newBlock("b", 2), newBlock("c", 0)) + .subsumedBy(newBlocksGroup(newBlock("a", 3), newBlock("b", 1)), 1), + is(false)); + + // ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] subsumedBy ['a'[3|3-8]:4, 'b'[1|1-6]:4] false + assertThat(newBlocksGroup(newBlock("a", 5), newBlock("b", 3), newBlock("c", 1)) + .subsumedBy(newBlocksGroup(newBlock("a", 3), newBlock("b", 1)), 1), + is(false)); + + // ['a'[6|6-11]:7, 'c'[2|2-7]:7] subsumedBy ['a'[3|3-8]:4, 'b'[1|1-6]:4] false + assertThat(newBlocksGroup(newBlock("a", 6), newBlock("c", 2)) + .subsumedBy(newBlocksGroup(newBlock("a", 3), newBlock("b", 1)), 1), + is(false)); + + // ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] subsumedBy ['a'[4|4-9]:5, 'b'[2|2-7]:5, 'c'[0|0-5]:5] true + assertThat(newBlocksGroup(newBlock("a", 5), newBlock("b", 3), newBlock("c", 1)) + .subsumedBy(newBlocksGroup(newBlock("a", 4), newBlock("b", 2), newBlock("c", 0)), 1), + is(true)); + + // ['a'[6|6-11]:7, 'c'[2|2-7]:7] subsumedBy ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] true + assertThat(newBlocksGroup(newBlock("a", 6), newBlock("c", 2)) + .subsumedBy(newBlocksGroup(newBlock("a", 5), newBlock("b", 3), newBlock("c", 1)), 1), + is(true)); + } + + /** + * Results for this test taken from results of work of naive implementation. + */ + @Test + public void testIntersect2() { + // ['a'[2|2-7]:3, 'b'[0|0-5]:3] + // intersect ['a'[3|3-8]:4, 'b'[1|1-6]:4] + // as ['a'[3|3-8]:4, 'b'[1|1-6]:4] + assertThat(newBlocksGroup(newBlock("a", 2), newBlock("b", 0)) + .intersect(newBlocksGroup(newBlock("a", 3), newBlock("b", 1))) + .size(), is(2)); + + // ['a'[3|3-8]:4, 'b'[1|1-6]:4] + // intersect ['a'[4|4-9]:5, 'b'[2|2-7]:5, 'c'[0|0-5]:5] + // as ['a'[4|4-9]:5, 'b'[2|2-7]:5] + assertThat(newBlocksGroup(newBlock("a", 3), newBlock("b", 1)) + .intersect(newBlocksGroup(newBlock("a", 4), newBlock("b", 2), newBlock("c", 0))) + .size(), is(2)); + + // ['a'[4|4-9]:5, 'b'[2|2-7]:5] + // intersect ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] + // as ['a'[5|5-10]:6, 'b'[3|3-8]:6] + assertThat(newBlocksGroup(newBlock("a", 4), newBlock("b", 2)) + .intersect(newBlocksGroup(newBlock("a", 5), newBlock("b", 3), newBlock("c", 1))) + .size(), is(2)); + + // ['a'[5|5-10]:6, 'b'[3|3-8]:6] + // intersect ['a'[6|6-11]:7, 'c'[2|2-7]:7] + // as ['a'[6|6-11]:7] + assertThat(newBlocksGroup(newBlock("a", 5), newBlock("b", 3)) + .intersect(newBlocksGroup(newBlock("a", 6), newBlock("c", 2))) + .size(), is(1)); + + // ['a'[4|4-9]:5, 'b'[2|2-7]:5, 'c'[0|0-5]:5] + // intersect ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] + // as ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] + assertThat(newBlocksGroup(newBlock("a", 4), newBlock("b", 2), newBlock("c", 0)) + .intersect(newBlocksGroup(newBlock("a", 5), newBlock("b", 3), newBlock("c", 1))) + .size(), is(3)); + + // ['a'[5|5-10]:6, 'b'[3|3-8]:6, 'c'[1|1-6]:6] + // intersect ['a'[6|6-11]:7, 'c'[2|2-7]:7] + // as ['a'[6|6-11]:7, 'c'[2|2-7]:7] + assertThat(newBlocksGroup(newBlock("a", 5), newBlock("b", 3), newBlock("c", 1)) + .intersect(newBlocksGroup(newBlock("a", 6), newBlock("c", 2))) + .size(), is(2)); + + // ['a'[6|6-11]:7, 'c'[2|2-7]:7] + // intersect ['a'[7|7-12]:8] + // as ['a'[7|7-12]:8] + assertThat(newBlocksGroup(newBlock("a", 6), newBlock("c", 7)) + .intersect(newBlocksGroup(newBlock("a", 7))) + .size(), is(1)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/FilterTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/FilterTest.java new file mode 100644 index 00000000000..9b6198d345f --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/FilterTest.java @@ -0,0 +1,193 @@ +/* + * 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.detector.original; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.Arrays; + +import org.junit.Test; +import org.sonar.duplications.index.CloneGroup; +import org.sonar.duplications.index.ClonePart; + +public class FilterTest { + + /** + * Given: + * <pre> + * c1: a[1-1] + * c2: a[1-1] + * </pre> + * Expected: + * reflexive - c1 in c1, + * antisymmetric - c1 in c2, c2 in c1, because c1 = c2 + */ + @Test + public void reflexive_and_antisymmetric() { + CloneGroup c1 = newCloneGroup(1, + newClonePart("a", 1)); + CloneGroup c2 = newCloneGroup(1, + newClonePart("a", 1)); + + assertThat(Filter.containsIn(c1, c1), is(true)); + assertThat(Filter.containsIn(c1, c2), is(true)); + assertThat(Filter.containsIn(c2, c1), is(true)); + } + + /** + * Given: + * <pre> + * c1: a[1-1] + * c2: a[2-2] + * </pre> + * Expected: c1 not in c2, c2 not in c1 + */ + @Test + public void start_index_in_C1_less_than_in_C2() { + CloneGroup c1 = newCloneGroup(1, + newClonePart("a", 1)); + CloneGroup c2 = newCloneGroup(1, + newClonePart("a", 2)); + + assertThat(Filter.containsIn(c1, c2), is(false)); + } + + /** + * Given: + * <pre> + * c1: a[0-0], a[2-2], b[0-0], b[2-2] + * c2: a[0-2], b[0-2] + * </pre> + * Expected: + * <pre> + * c1 in c2 (all parts of c1 covered by parts of c2 and all resources the same) + * c2 not in c1 (not all parts of c2 covered by parts of c1 and all resources the same) + * </pre> + */ + @Test + public void one_part_of_C2_covers_two_parts_of_C1() { + // Note that line numbers don't matter for method which we test. + CloneGroup c1 = newCloneGroup(1, + newClonePart("a", 0), + newClonePart("a", 2), + newClonePart("b", 0), + newClonePart("b", 2)); + CloneGroup c2 = newCloneGroup(3, + newClonePart("a", 0), + newClonePart("b", 0)); + + assertThat(Filter.containsIn(c1, c2), is(true)); + assertThat(Filter.containsIn(c2, c1), is(false)); + } + + /** + * Given: + * <pre> + * c1: a[0-0], a[2-2] + * c2: a[0-2], b[0-2] + * </pre> + * Expected: + * <pre> + * c1 not in c2 (all parts of c1 covered by parts of c2, but different resources) + * c2 not in c1 (not all parts of c2 covered by parts of c1 and different resources) + * </pre> + */ + @Test + public void different_resources() { + CloneGroup c1 = newCloneGroup(1, + newClonePart("a", 0), + newClonePart("a", 2)); + CloneGroup c2 = newCloneGroup(3, + newClonePart("a", 0), + newClonePart("b", 0)); + + assertThat(Filter.containsIn(c1, c2), is(false)); + assertThat(Filter.containsIn(c2, c1), is(false)); + } + + /** + * Given: + * <pre> + * c1: a[2-2] + * c2: a[0-1], a[2-3] + * </pre> + * Expected: + * <pre> + * c1 in c2 + * c2 not in c1 + * </pre> + */ + @Test + public void second_part_of_C2_covers_first_part_of_C1() { + CloneGroup c1 = newCloneGroup(1, + newClonePart("a", 2)); + CloneGroup c2 = newCloneGroup(2, + newClonePart("a", 0), + newClonePart("a", 2)); + + assertThat(Filter.containsIn(c1, c2), is(true)); + assertThat(Filter.containsIn(c2, c1), is(false)); + } + + /** + * Given: + * <pre> + * c1: a[0-2] + * c2: a[0-0] + * </pre> + * Expected: + * <pre> + * c1 not in c2 + * </pre> + */ + @Test + public void length_of_C1_bigger_than_length_of_C2() { + CloneGroup c1 = spy(newCloneGroup(3, + newClonePart("a", 0))); + CloneGroup c2 = spy(newCloneGroup(1, + newClonePart("a", 0))); + + assertThat(Filter.containsIn(c1, c2), is(false)); + // containsIn method should check only origin and length - no need to compare all parts + verify(c1).getCloneUnitLength(); + verify(c2).getCloneUnitLength(); + verifyNoMoreInteractions(c1); + verifyNoMoreInteractions(c2); + } + + /** + * Creates new part with specified resourceId and unitStart, and 0 for lineStart and lineEnd. + */ + private ClonePart newClonePart(String resourceId, int unitStart) { + return new ClonePart(resourceId, unitStart, 0, 0); + } + + /** + * Creates new group from list of parts, origin - is a first part from list. + */ + private CloneGroup newCloneGroup(int len, ClonePart... parts) { + return new CloneGroup(len, parts[0], Arrays.asList(parts)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/OriginalCloneDetectionAlgorithmTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/OriginalCloneDetectionAlgorithmTest.java new file mode 100644 index 00000000000..e22faf753a9 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/detector/original/OriginalCloneDetectionAlgorithmTest.java @@ -0,0 +1,512 @@ +/* + * 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.detector.original; + +import static org.hamcrest.Matchers.hasItem; +import static org.hamcrest.Matchers.is; +import static org.hamcrest.Matchers.sameInstance; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; + +import org.junit.Rule; +import org.junit.Test; +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; +import org.sonar.duplications.index.CloneGroup; +import org.sonar.duplications.index.CloneIndex; +import org.sonar.duplications.index.ClonePart; +import org.sonar.duplications.index.MemoryCloneIndex; +import org.sonar.duplications.junit.TestNamePrinter; + +import com.google.common.collect.Lists; + +public class OriginalCloneDetectionAlgorithmTest { + + @Rule + public TestNamePrinter name = new TestNamePrinter(); + + private static int LINES_PER_BLOCK = 5; + + /** + * To simplify testing we assume that each block starts from a new line and contains {@link #LINES_PER_BLOCK} lines, + * so we can simply use index and hash. + */ + private static Block newBlock(String resourceId, ByteArray hash, int index) { + return new Block(resourceId, hash, index, index, index + LINES_PER_BLOCK); + } + + private static ClonePart newClonePart(String resourceId, int unitStart, int cloneUnitLength) { + return new ClonePart(resourceId, unitStart, unitStart, unitStart + cloneUnitLength + LINES_PER_BLOCK - 1); + } + + /** + * Given: + * <pre> + * y: 2 3 4 5 + * z: 3 4 + * x: 1 2 3 4 5 6 + * </pre> + * Expected: + * <pre> + * x-y (2 3 4 5) + * x-y-z (3 4) + * </pre> + */ + @Test + public void exampleFromPaper() { + CloneIndex cloneIndex = createIndex( + blocksForResource("y").withHashes("2", "3", "4", "5"), + blocksForResource("z").withHashes("3", "4")); + List<Block> fileBlocks = blocksForResource("x").withHashes("1", "2", "3", "4", "5", "6"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + assertThat(clones.size(), is(2)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(4)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("x", 1, 4))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("x", 1, 4))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("y", 0, 4))); + + clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(2)); + assertThat(clone.getCloneParts().size(), is(3)); + assertThat(clone.getOriginPart(), is(newClonePart("x", 2, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("x", 2, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("y", 1, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("z", 0, 2))); + } + + /** + * Given: + * <pre> + * a: 2 3 4 5 + * b: 3 4 + * c: 1 2 3 4 5 6 + * </pre> + * Expected: + * <pre> + * c-a (2 3 4 5) + * c-a-b (3 4) + * </pre> + */ + @Test + public void exampleFromPaperWithModifiedResourceIds() { + CloneIndex cloneIndex = createIndex( + blocksForResource("a").withHashes("2", "3", "4", "5"), + blocksForResource("b").withHashes("3", "4")); + List<Block> fileBlocks = blocksForResource("c").withHashes("1", "2", "3", "4", "5", "6"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + assertThat(clones.size(), is(2)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(4)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("c", 1, 4))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("c", 1, 4))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 4))); + + clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(2)); + assertThat(clone.getCloneParts().size(), is(3)); + assertThat(clone.getOriginPart(), is(newClonePart("c", 2, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("c", 2, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 1, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 2))); + } + + /** + * Given: + * <pre> + * b: 3 4 5 6 + * c: 5 6 7 + * a: 1 2 3 4 5 6 7 8 9 + * </pre> + * Expected: + * <pre> + * a-b (3 4 5 6) + * a-b-c (5 6) + * a-c (5 6 7) + * </pre> + */ + @Test + public void example1() { + CloneIndex cloneIndex = createIndex( + blocksForResource("b").withHashes("3", "4", "5", "6"), + blocksForResource("c").withHashes("5", "6", "7")); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "3", "4", "5", "6", "7", "8", "9"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + assertThat(clones.size(), is(3)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(4)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 2, 4))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 2, 4))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 4))); + + clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(2)); + assertThat(clone.getCloneParts().size(), is(3)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 4, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 4, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 2, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("c", 0, 2))); + + clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(3)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 4, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 4, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("c", 0, 3))); + } + + /** + * Given: + * <pre> + * b: 1 2 3 4 1 2 3 4 1 2 3 4 + * c: 1 2 3 4 + * a: 1 2 3 4 5 + * </pre> + * Expected: + * <pre> + * a-b-b-b-c (1 2 3 4) + * </pre> + */ + @Test + public void example2() { + CloneIndex cloneIndex = createIndex( + blocksForResource("b").withHashes("1", "2", "3", "4", "1", "2", "3", "4", "1", "2", "3", "4"), + blocksForResource("c").withHashes("1", "2", "3", "4")); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "3", "5"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + assertThat(clones.size(), is(1)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(3)); + assertThat(clone.getCloneParts().size(), is(5)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 4, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 8, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("c", 0, 3))); + } + + /** + * Given: + * <pre> + * b: 1 2 3 4 + * a: 1 2 3 + * </pre> + * Expected clone which ends at the end of file "a": + * <pre> + * a-b (1 2 3) + * </pre> + */ + @Test + public void problemWithEndOfFile() { + CloneIndex cloneIndex = createIndex( + blocksForResource("b").withHashes("1", "2", "3", "4")); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "3"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + assertThat(clones.size(), is(1)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(3)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 3))); + } + + /** + * Test for problem, which was described in original paper - same clone would be reported twice. + * Given: + * <pre> + * a: 1 2 3 1 2 4 + * </pre> + * Expected only one clone: + * <pre> + * a-a (1 2) + * </pre> + */ + @Test + public void clonesInFileItself() { + CloneIndex cloneIndex = createIndex(); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "3", "1", "2", "4"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + + assertThat(clones.size(), is(1)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(2)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 3, 2))); + } + + /** + * Given: + * <pre> + * b: 1 2 1 2 + * a: 1 2 1 + * </pre> + * Expected: + * <pre> + * a-b-b (1 2) + * a-b (1 2 1) + * </pre> + * "a-a-b-b (1)" should not be reported, because fully covered by "a-b (1 2 1)" + */ + @Test + public void covered() { + CloneIndex cloneIndex = createIndex( + blocksForResource("b").withHashes("1", "2", "1", "2")); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "1"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + + assertThat(clones.size(), is(2)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 2, 2))); + + clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(3)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 3))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 3))); + } + + /** + * Given: + * <pre> + * b: 1 2 1 2 1 2 1 + * a: 1 2 1 2 1 2 + * </pre> + * Expected: + * <pre> + * a-b-b (1 2 1 2 1) - note that there is overlapping among parts for "b" + * a-b (1 2 1 2 1 2) + * </pre> + */ + @Test + public void problemWithNestedCloneGroups() { + CloneIndex cloneIndex = createIndex( + blocksForResource("b").withHashes("1", "2", "1", "2", "1", "2", "1")); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "1", "2", "1", "2"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + + assertThat(clones.size(), is(2)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(5)); + assertThat(clone.getCloneParts().size(), is(3)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 5))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 5))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 5))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 2, 5))); + + clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(6)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 6))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 6))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 6))); + } + + /** + * Given: + * <pre> + * a: 1 2 3 + * b: 1 2 4 + * a: 1 2 5 + * </pre> + * Expected: + * <pre> + * a-b (1 2) - instead of "a-a-b", which will be the case if file from index not ignored + * </pre> + */ + @Test + public void fileAlreadyInIndex() { + CloneIndex cloneIndex = createIndex( + blocksForResource("a").withHashes("1", "2", "3"), + blocksForResource("b").withHashes("1", "2", "4")); + // Note about blocks with hashes "3", "4" and "5": those blocks here in order to not face another problem - with EOF (see separate test) + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "5"); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + + assertThat(clones.size(), is(1)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(2)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(newClonePart("a", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("a", 0, 2))); + assertThat(clone.getCloneParts(), hasItem(newClonePart("b", 0, 2))); + } + + /** + * Given: file with repeated hashes + * Expected: only one query of index for each unique hash + */ + @Test + public void only_one_query_of_index_for_each_unique_hash() { + CloneIndex index = spy(createIndex()); + List<Block> fileBlocks = + blocksForResource("a").withHashes("1", "2", "1", "2"); + OriginalCloneDetectionAlgorithm.detect(index, fileBlocks); + + verify(index).getBySequenceHash(new ByteArray("1".getBytes())); + verify(index).getBySequenceHash(new ByteArray("2".getBytes())); + verifyNoMoreInteractions(index); + } + + /** + * Given file with two lines, containing following statements: + * <pre> + * 0: A,B,A,B + * 1: A,B,A + * </pre> + * with block size 5 each block will span both lines, and hashes will be: + * <pre> + * A,B,A,B,A=1 + * B,A,B,A,B=2 + * A,B,A,B,A=1 + * </pre> + * Expected: one clone with two parts, which contain exactly the same lines + */ + @Test + public void same_lines_but_different_indexes() { + CloneIndex cloneIndex = createIndex(); + List<Block> fileBlocks = Arrays.asList( + new Block("a", new ByteArray("1".getBytes()), 0, 0, 1), + new Block("a", new ByteArray("2".getBytes()), 1, 0, 1), + new Block("a", new ByteArray("1".getBytes()), 2, 0, 1)); + List<CloneGroup> clones = OriginalCloneDetectionAlgorithm.detect(cloneIndex, fileBlocks); + print(clones); + + assertThat(clones.size(), is(1)); + Iterator<CloneGroup> clonesIterator = clones.iterator(); + + CloneGroup clone = clonesIterator.next(); + assertThat(clone.getCloneUnitLength(), is(1)); + assertThat(clone.getCloneParts().size(), is(2)); + assertThat(clone.getOriginPart(), is(new ClonePart("a", 0, 0, 1))); + assertThat(clone.getCloneParts(), hasItem(new ClonePart("a", 0, 0, 1))); + assertThat(clone.getCloneParts(), hasItem(new ClonePart("a", 2, 0, 1))); + } + + /** + * Given: empty list of blocks for file + * Expected: {@link Collections#EMPTY_LIST} + */ + @Test + public void shouldReturnEmptyListWhenNoBlocksForFile() { + List<CloneGroup> result = OriginalCloneDetectionAlgorithm.detect(null, new ArrayList<Block>()); + assertThat(result, sameInstance(Collections.EMPTY_LIST)); + } + + private void print(List<CloneGroup> clones) { + for (CloneGroup clone : clones) { + System.out.println(clone); + } + System.out.println(); + } + + private static CloneIndex createIndex(List<Block>... blocks) { + CloneIndex cloneIndex = new MemoryCloneIndex(); + for (List<Block> b : blocks) { + for (Block block : b) { + cloneIndex.insert(block); + } + } + return cloneIndex; + } + + private static BlocksBuilder blocksForResource(String resourceId) { + return new BlocksBuilder(resourceId); + } + + private static class BlocksBuilder { + String resourceId; + + public BlocksBuilder(String resourceId) { + this.resourceId = resourceId; + } + + List<Block> withHashes(String... hashes) { + ByteArray[] arrays = new ByteArray[hashes.length]; + for (int i = 0; i < hashes.length; i++) { + arrays[i] = new ByteArray(hashes[i].getBytes()); + } + return withHashes(arrays); + } + + List<Block> withHashes(ByteArray... hashes) { + List<Block> result = Lists.newArrayList(); + int index = 0; + for (ByteArray hash : hashes) { + result.add(newBlock(resourceId, hash, index)); + index++; + } + return result; + } + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/index/DataUtilsTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/index/DataUtilsTest.java new file mode 100644 index 00000000000..c210a4c8e05 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/index/DataUtilsTest.java @@ -0,0 +1,90 @@ +/* + * 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.index; + +import static org.hamcrest.Matchers.equalTo; +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +import java.util.Arrays; + +import org.junit.Test; + +public class DataUtilsTest { + + @Test + public void testSort() { + int[] expected = new int[200]; + int[] actual = new int[expected.length]; + for (int i = 0; i < expected.length; i++) { + expected[i] = (int) (Math.random() * 900); + actual[i] = expected[i]; + } + Arrays.sort(expected); + DataUtils.sort(new SimpleSortable(actual, actual.length)); + assertThat(actual, equalTo(expected)); + } + + @Test + public void testSearch() { + int[] a = new int[] { 1, 2, 4, 4, 4, 5, 0 }; + SimpleSortable sortable = new SimpleSortable(a, a.length - 1); + // search 4 + a[a.length - 1] = 4; + assertThat(DataUtils.binarySearch(sortable), is(2)); + // search 5 + a[a.length - 1] = 5; + assertThat(DataUtils.binarySearch(sortable), is(5)); + // search -5 + a[a.length - 1] = -5; + assertThat(DataUtils.binarySearch(sortable), is(0)); + // search 10 + a[a.length - 1] = 10; + assertThat(DataUtils.binarySearch(sortable), is(6)); + // search 3 + a[a.length - 1] = 3; + assertThat(DataUtils.binarySearch(sortable), is(2)); + } + + class SimpleSortable implements DataUtils.Sortable { + private final int[] a; + private final int size; + + public SimpleSortable(int[] a, int size) { + this.a = a; + this.size = size; + } + + public int size() { + return size; + } + + public void swap(int i, int j) { + int tmp = a[i]; + a[i] = a[j]; + a[j] = tmp; + } + + public boolean isLess(int i, int j) { + return a[i] < a[j]; + } + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/index/MemoryCloneIndexTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/index/MemoryCloneIndexTest.java new file mode 100644 index 00000000000..fc44357d3aa --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/index/MemoryCloneIndexTest.java @@ -0,0 +1,102 @@ +/* + * 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.index; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.junit.Assert.assertTrue; + +import java.util.Collection; + +import org.junit.Before; +import org.junit.Test; +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; + +public class MemoryCloneIndexTest { + + private CloneIndex cloneIndex; + + @Before + public void initialize() { + cloneIndex = new MemoryCloneIndex(); + } + + @Test + public void byFileName() { + Block tuple1 = new Block("a", new ByteArray(0), 0, 0, 10); + Block tuple2 = new Block("a", new ByteArray(0), 1, 10, 20); + + assertThat(cloneIndex.getByResourceId("a").size(), is(0)); + + cloneIndex.insert(tuple1); + assertThat(cloneIndex.getByResourceId("a").size(), is(1)); + + cloneIndex.insert(tuple2); + assertThat(cloneIndex.getByResourceId("a").size(), is(2)); + } + + @Test + public void bySequenceHash() { + Block tuple1 = new Block("a", new ByteArray(0), 0, 0, 5); + Block tuple2 = new Block("a", new ByteArray(0), 1, 1, 6); + + assertThat(cloneIndex.getBySequenceHash(new ByteArray(0)).size(), is(0)); + + cloneIndex.insert(tuple1); + assertThat(cloneIndex.getBySequenceHash(new ByteArray(0)).size(), is(1)); + + cloneIndex.insert(tuple2); + assertThat(cloneIndex.getBySequenceHash(new ByteArray(0)).size(), is(2)); + } + + @Test + public void insertSame() { + Block tuple = new Block("a", new ByteArray(0), 0, 0, 5); + Block tupleSame = new Block("a", new ByteArray(0), 0, 0, 5); + + assertThat(cloneIndex.getByResourceId("a").size(), is(0)); + assertThat(cloneIndex.getBySequenceHash(new ByteArray(0)).size(), is(0)); + + cloneIndex.insert(tuple); + assertThat(cloneIndex.getByResourceId("a").size(), is(1)); + assertThat(cloneIndex.getBySequenceHash(new ByteArray(0)).size(), is(1)); + + cloneIndex.insert(tupleSame); + assertThat(cloneIndex.getByResourceId("a").size(), is(1)); + assertThat(cloneIndex.getBySequenceHash(new ByteArray(0)).size(), is(1)); + } + + @Test + public void testSorted() { + for (int i = 0; i < 10; i++) { + cloneIndex.insert(new Block("a", new ByteArray(1), 10 - i, i, i + 5)); + } + assertThat(cloneIndex.getByResourceId("a").size(), is(10)); + assertThat(cloneIndex.getBySequenceHash(new ByteArray(1)).size(), is(10)); + + Collection<Block> set = cloneIndex.getByResourceId("a"); + int prevStatementIndex = 0; + for (Block tuple : set) { + assertTrue(tuple.getIndexInFile() > prevStatementIndex); + prevStatementIndex = tuple.getIndexInFile(); + } + } +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/index/PackedMemoryCloneIndexTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/index/PackedMemoryCloneIndexTest.java new file mode 100644 index 00000000000..4fc2c2b11a4 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/index/PackedMemoryCloneIndexTest.java @@ -0,0 +1,116 @@ +/* + * 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.index; + +import static org.hamcrest.Matchers.is; +import static org.hamcrest.Matchers.sameInstance; +import static org.junit.Assert.assertThat; + +import java.util.Collection; + +import org.junit.Before; +import org.junit.Test; +import org.sonar.duplications.block.Block; +import org.sonar.duplications.block.ByteArray; + +public class PackedMemoryCloneIndexTest { + + private PackedMemoryCloneIndex index; + + @Before + public void setUp() { + index = new PackedMemoryCloneIndex(); + } + + @Test + public void test() { + index.insert(newBlock("a", 1)); + index.insert(newBlock("a", 2)); + index.insert(newBlock("b", 1)); + index.insert(newBlock("c", 1)); + index.insert(newBlock("d", 1)); + index.insert(newBlock("e", 1)); + index.insert(newBlock("e", 2)); + index.insert(newBlock("e", 3)); + + assertThat(index.getBySequenceHash(new ByteArray(1L)).size(), is(5)); + assertThat(index.getBySequenceHash(new ByteArray(2L)).size(), is(2)); + assertThat(index.getBySequenceHash(new ByteArray(3L)).size(), is(1)); + assertThat(index.getBySequenceHash(new ByteArray(4L)).size(), is(0)); + assertThat(index.getByResourceId("a").size(), is(2)); + assertThat(index.getByResourceId("b").size(), is(1)); + assertThat(index.getByResourceId("e").size(), is(3)); + assertThat(index.getByResourceId("does not exist").size(), is(0)); + } + + /** + * When: query by a hash value. + * Expected: all blocks should have same hash, which presented in the form of the same object. + */ + @Test + public void should_construct_blocks_with_normalized_hash() { + index.insert(newBlock("a", 1)); + index.insert(newBlock("b", 1)); + index.insert(newBlock("c", 1)); + ByteArray requestedHash = new ByteArray(1L); + Collection<Block> blocks = index.getBySequenceHash(requestedHash); + assertThat(blocks.size(), is(3)); + for (Block block : blocks) { + assertThat(block.getBlockHash(), sameInstance(requestedHash)); + } + } + + /** + * Given: index with initial capacity 1. + * Expected: size and capacity should be increased after insertion of two blocks. + */ + @Test + public void should_increase_capacity() { + CloneIndex index = new PackedMemoryCloneIndex(8, 1); + index.insert(newBlock("a", 1)); + index.insert(newBlock("a", 2)); + assertThat(index.getByResourceId("a").size(), is(2)); + } + + /** + * Given: index, which accepts blocks with 4-byte hash. + * Expected: exception during insertion of block with 8-byte hash. + */ + @Test(expected = IllegalArgumentException.class) + public void attempt_to_insert_hash_of_incorrect_size() { + CloneIndex index = new PackedMemoryCloneIndex(4, 1); + index.insert(newBlock("a", 1)); + } + + /** + * Given: index, which accepts blocks with 4-byte hash. + * Expected: exception during search by 8-byte hash. + */ + @Test(expected = IllegalArgumentException.class) + public void attempt_to_find_hash_of_incorrect_size() { + CloneIndex index = new PackedMemoryCloneIndex(4, 1); + index.getBySequenceHash(new ByteArray(1L)); + } + + private static Block newBlock(String resourceId, long hash) { + return new Block(resourceId, new ByteArray(hash), 1, 1, 1); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/java/JavaStatementBuilderTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/java/JavaStatementBuilderTest.java new file mode 100644 index 00000000000..2267fa8a125 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/java/JavaStatementBuilderTest.java @@ -0,0 +1,160 @@ +/* + * 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.java; + +import static org.hamcrest.Matchers.is; +import static org.hamcrest.number.OrderingComparisons.greaterThan; +import static org.junit.Assert.assertThat; + +import java.io.File; +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.DuplicationsTestUtil; +import org.sonar.duplications.statement.Statement; +import org.sonar.duplications.statement.StatementChunker; +import org.sonar.duplications.token.TokenChunker; + +public class JavaStatementBuilderTest { + + private TokenChunker tokenChunker = JavaTokenProducer.build(); + private StatementChunker statementChunker = JavaStatementBuilder.build(); + + private List<Statement> chunk(String sourceCode) { + return statementChunker.chunk(tokenChunker.chunk(sourceCode)); + } + + @Test + public void shouldIgnoreImportStatement() { + assertThat(chunk("import org.sonar.duplications.java;").size(), is(0)); + } + + @Test + public void shouldIgnorePackageStatement() { + assertThat(chunk("package org.sonar.duplications.java;").size(), is(0)); + } + + @Test + public void shouldHandleAnnotation() { + List<Statement> statements = chunk("" + + "@Entity" + + "@Table(name = \"properties\")" + + "@Column(updatable = true, nullable = true)"); + assertThat(statements.size(), is(3)); + assertThat(statements.get(0).getValue(), is("@Entity")); + assertThat(statements.get(1).getValue(), is("@Table(name=$CHARS)")); + assertThat(statements.get(2).getValue(), is("@Column(updatable=true,nullable=true)")); + } + + @Test + public void shouldHandleIf() { + List<Statement> statements = chunk("if (a > b) { something(); }"); + assertThat(statements.size(), is(2)); + assertThat(statements.get(0).getValue(), is("if(a>b)")); + assertThat(statements.get(1).getValue(), is("something()")); + + statements = chunk("if (a > b) { something(); } else { somethingOther(); }"); + assertThat(statements.size(), is(4)); + assertThat(statements.get(0).getValue(), is("if(a>b)")); + assertThat(statements.get(1).getValue(), is("something()")); + assertThat(statements.get(2).getValue(), is("else")); + assertThat(statements.get(3).getValue(), is("somethingOther()")); + + statements = chunk("if (a > 0) { something(); } else if (a == 0) { somethingOther(); }"); + assertThat(statements.size(), is(4)); + assertThat(statements.get(0).getValue(), is("if(a>$NUMBER)")); + assertThat(statements.get(1).getValue(), is("something()")); + assertThat(statements.get(2).getValue(), is("elseif(a==$NUMBER)")); + assertThat(statements.get(3).getValue(), is("somethingOther()")); + } + + @Test + public void shouldHandleFor() { + List<Statement> statements = chunk("for (int i = 0; i < 10; i++) { something(); }"); + assertThat(statements.size(), is(2)); + assertThat(statements.get(0).getValue(), is("for(inti=$NUMBER;i<$NUMBER;i++)")); + assertThat(statements.get(1).getValue(), is("something()")); + + statements = chunk("for (Item item : items) { something(); }"); + assertThat(statements.size(), is(2)); + assertThat(statements.get(0).getValue(), is("for(Itemitem:items)")); + assertThat(statements.get(1).getValue(), is("something()")); + } + + @Test + public void shouldHandleWhile() { + List<Statement> statements = chunk("while (i < args.length) { something(); }"); + assertThat(statements.size(), is(2)); + assertThat(statements.get(0).getValue(), is("while(i<args.length)")); + assertThat(statements.get(1).getValue(), is("something()")); + + statements = chunk("while (true);"); + assertThat(statements.size(), is(1)); + assertThat(statements.get(0).getValue(), is("while(true)")); + } + + @Test + public void shouldHandleDoWhile() { + List<Statement> statements = chunk("do { something(); } while (true);"); + assertThat(statements.size(), is(3)); + assertThat(statements.get(0).getValue(), is("do")); + assertThat(statements.get(1).getValue(), is("something()")); + assertThat(statements.get(2).getValue(), is("while(true)")); + } + + @Test + public void shouldHandleSwitch() { + List<Statement> statements = chunk("" + + "switch (month) {" + + " case 1 : monthString=\"January\"; break;" + + " case 2 : monthString=\"February\"; break;" + + " default: monthString=\"Invalid\";"); + assertThat(statements.size(), is(9)); + assertThat(statements.get(0).getValue(), is("switch(month)")); + assertThat(statements.get(1).getValue(), is("case$NUMBER:")); + assertThat(statements.get(2).getValue(), is("monthString=$CHARS")); + assertThat(statements.get(3).getValue(), is("break")); + assertThat(statements.get(4).getValue(), is("case$NUMBER:")); + assertThat(statements.get(5).getValue(), is("monthString=$CHARS")); + assertThat(statements.get(6).getValue(), is("break")); + assertThat(statements.get(7).getValue(), is("default:")); + assertThat(statements.get(8).getValue(), is("monthString=$CHARS")); + } + + @Test + public void shouldHandleArray() { + List<Statement> statements = chunk("new Integer[][] { { 1, 2 }, {3, 4} };"); + assertThat(statements.size(), is(4)); + assertThat(statements.get(0).getValue(), is("newInteger[][]")); + assertThat(statements.get(1).getValue(), is("$NUMBER,$NUMBER")); + assertThat(statements.get(2).getValue(), is(",")); + assertThat(statements.get(3).getValue(), is("$NUMBER,$NUMBER")); + } + + @Test + public void realExamples() { + File testFile = DuplicationsTestUtil.findFile("/java/MessageResources.java"); + assertThat(statementChunker.chunk(tokenChunker.chunk(testFile)).size(), greaterThan(0)); + + testFile = DuplicationsTestUtil.findFile("/java/RequestUtils.java"); + assertThat(statementChunker.chunk(tokenChunker.chunk(testFile)).size(), greaterThan(0)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/java/JavaTokenProducerTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/java/JavaTokenProducerTest.java new file mode 100644 index 00000000000..285cdf2c61e --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/java/JavaTokenProducerTest.java @@ -0,0 +1,293 @@ +/* + * 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.java; + +import static org.hamcrest.Matchers.is; +import static org.hamcrest.number.OrderingComparisons.greaterThan; +import static org.junit.Assert.assertThat; + +import java.io.File; +import java.util.Arrays; +import java.util.List; + +import org.hamcrest.Matcher; +import org.junit.Test; +import org.sonar.duplications.DuplicationsTestUtil; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenChunker; + +import com.google.common.collect.Lists; + +/** + * See <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html">The Java Language Specification, Third Edition: Lexical Structure</a> + * + * TODO Java 7 features: Binary Integer Literals, Using Underscore Characters in Numeric Literals + * TODO add more complex example + */ +public class JavaTokenProducerTest { + + private TokenChunker chunker = JavaTokenProducer.build(); + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.6">White Space</a> + */ + @Test + public void shouldIgnoreWhitespaces() { + assertThat(chunk(" \t\f\n\r"), isTokens()); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.7">Comments</a> + */ + @Test + public void shouldIgnoreEndOfLineComment() { + assertThat(chunk("// This is a comment"), isTokens()); + assertThat(chunk("// This is a comment \n and_this_is_not"), isTokens(new Token("and_this_is_not", 2, 1))); + } + + @Test + public void shouldIgnoreTraditionalComment() { + assertThat(chunk("/* This is a comment \n and the second line */"), isTokens()); + assertThat(chunk("/** This is a javadoc \n and the second line */"), isTokens()); + assertThat(chunk("/* this \n comment /* \n // /** ends \n here: */"), isTokens()); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.8">Identifiers</a> + */ + @Test + public void shouldPreserveIdentifiers() { + assertThat(chunk("String"), isTokens(new Token("String", 1, 0))); + assertThat(chunk("i3"), isTokens(new Token("i3", 1, 0))); + assertThat(chunk("MAX_VALUE"), isTokens(new Token("MAX_VALUE", 1, 0))); + assertThat(chunk("isLetterOrDigit"), isTokens(new Token("isLetterOrDigit", 1, 0))); + + assertThat(chunk("_"), isTokens(new Token("_", 1, 0))); + assertThat(chunk("_123_"), isTokens(new Token("_123_", 1, 0))); + assertThat(chunk("_Field"), isTokens(new Token("_Field", 1, 0))); + assertThat(chunk("_Field5"), isTokens(new Token("_Field5", 1, 0))); + + assertThat(chunk("$"), isTokens(new Token("$", 1, 0))); + assertThat(chunk("$field"), isTokens(new Token("$field", 1, 0))); + + assertThat(chunk("i2j"), isTokens(new Token("i2j", 1, 0))); + assertThat(chunk("from1to4"), isTokens(new Token("from1to4", 1, 0))); + + assertThat("identifier with unicode", chunk("αβγ"), isTokens(new Token("αβγ", 1, 0))); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.9">Keywords</a> + */ + @Test + public void shouldPreserverKeywords() { + assertThat(chunk("private static final"), isTokens(new Token("private", 1, 0), new Token("static", 1, 8), new Token("final", 1, 15))); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.10.1">Integer Literals</a> + */ + @Test + public void shouldNormalizeDecimalIntegerLiteral() { + assertThat(chunk("543"), isNumericLiteral()); + assertThat(chunk("543l"), isNumericLiteral()); + assertThat(chunk("543L"), isNumericLiteral()); + } + + @Test + public void shouldNormalizeOctalIntegerLiteral() { + assertThat(chunk("077"), isNumericLiteral()); + assertThat(chunk("077l"), isNumericLiteral()); + assertThat(chunk("077L"), isNumericLiteral()); + } + + @Test + public void shouldNormalizeHexIntegerLiteral() { + assertThat(chunk("0xFF"), isNumericLiteral()); + assertThat(chunk("0xFFl"), isNumericLiteral()); + assertThat(chunk("0xFFL"), isNumericLiteral()); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.10.2">Floating-Point Literals</a> + */ + @Test + public void shouldNormalizeDecimalFloatingPointLiteral() { + // with dot at the end + assertThat(chunk("1234."), isNumericLiteral()); + assertThat(chunk("1234.E1"), isNumericLiteral()); + assertThat(chunk("1234.e+1"), isNumericLiteral()); + assertThat(chunk("1234.E-1"), isNumericLiteral()); + assertThat(chunk("1234.f"), isNumericLiteral()); + + // with dot between + assertThat(chunk("12.34"), isNumericLiteral()); + assertThat(chunk("12.34E1"), isNumericLiteral()); + assertThat(chunk("12.34e+1"), isNumericLiteral()); + assertThat(chunk("12.34E-1"), isNumericLiteral()); + + assertThat(chunk("12.34f"), isNumericLiteral()); + assertThat(chunk("12.34E1F"), isNumericLiteral()); + assertThat(chunk("12.34E+1d"), isNumericLiteral()); + assertThat(chunk("12.34e-1D"), isNumericLiteral()); + + // with dot at the beginning + assertThat(chunk(".1234"), isNumericLiteral()); + assertThat(chunk(".1234e1"), isNumericLiteral()); + assertThat(chunk(".1234E+1"), isNumericLiteral()); + assertThat(chunk(".1234E-1"), isNumericLiteral()); + + assertThat(chunk(".1234f"), isNumericLiteral()); + assertThat(chunk(".1234E1F"), isNumericLiteral()); + assertThat(chunk(".1234e+1d"), isNumericLiteral()); + assertThat(chunk(".1234E-1D"), isNumericLiteral()); + + // without dot + assertThat(chunk("1234e1"), isNumericLiteral()); + assertThat(chunk("1234E+1"), isNumericLiteral()); + assertThat(chunk("1234E-1"), isNumericLiteral()); + + assertThat(chunk("1234E1f"), isNumericLiteral()); + assertThat(chunk("1234e+1d"), isNumericLiteral()); + assertThat(chunk("1234E-1D"), isNumericLiteral()); + } + + @Test + public void shouldNormalizeHexadecimalFloatingPointLiteral() { + // with dot at the end + assertThat(chunk("0xAF."), isNumericLiteral()); + assertThat(chunk("0XAF.P1"), isNumericLiteral()); + assertThat(chunk("0xAF.p+1"), isNumericLiteral()); + assertThat(chunk("0XAF.p-1"), isNumericLiteral()); + assertThat(chunk("0xAF.f"), isNumericLiteral()); + + // with dot between + assertThat(chunk("0XAF.BC"), isNumericLiteral()); + assertThat(chunk("0xAF.BCP1"), isNumericLiteral()); + assertThat(chunk("0XAF.BCp+1"), isNumericLiteral()); + assertThat(chunk("0xAF.BCP-1"), isNumericLiteral()); + + assertThat(chunk("0xAF.BCf"), isNumericLiteral()); + assertThat(chunk("0xAF.BCp1F"), isNumericLiteral()); + assertThat(chunk("0XAF.BCP+1d"), isNumericLiteral()); + assertThat(chunk("0XAF.BCp-1D"), isNumericLiteral()); + + // without dot + assertThat(chunk("0xAFp1"), isNumericLiteral()); + assertThat(chunk("0XAFp+1"), isNumericLiteral()); + assertThat(chunk("0xAFp-1"), isNumericLiteral()); + + assertThat(chunk("0XAFp1f"), isNumericLiteral()); + assertThat(chunk("0xAFp+1d"), isNumericLiteral()); + assertThat(chunk("0XAFp-1D"), isNumericLiteral()); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.10.3">Boolean Literals</a> + */ + @Test + public void shouldPreserveBooleanLiterals() { + assertThat(chunk("true false"), isTokens(new Token("true", 1, 0), new Token("false", 1, 5))); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.10.4">Character Literals</a> + */ + @Test + public void shouldNormalizeCharacterLiterals() { + assertThat("single character", chunk("'a'"), isStringLiteral()); + assertThat("escaped LF", chunk("'\\n'"), isStringLiteral()); + assertThat("escaped quote", chunk("'\\''"), isStringLiteral()); + assertThat("octal escape", chunk("'\\177'"), isStringLiteral()); + assertThat("unicode escape", chunk("'\\u03a9'"), isStringLiteral()); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.10.5">String Literals</a> + */ + @Test + public void shouldNormalizeStringLiterals() { + assertThat("regular string", chunk("\"string\""), isStringLiteral()); + assertThat("empty string", chunk("\"\""), isStringLiteral()); + assertThat("escaped LF", chunk("\"\\n\""), isStringLiteral()); + assertThat("escaped double quotes", chunk("\"string, which contains \\\"escaped double quotes\\\"\""), isStringLiteral()); + assertThat("octal escape", chunk("\"string \\177\""), isStringLiteral()); + assertThat("unicode escape", chunk("\"string \\u03a9\""), isStringLiteral()); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.10.7">The Null Literal</a> + */ + @Test + public void shouldPreserverNullLiteral() { + assertThat(chunk("null"), isTokens(new Token("null", 1, 0))); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.11">Separators</a> + */ + @Test + public void shouldPreserveSeparators() { + assertThat(chunk("(){}[];,."), isTokens( + new Token("(", 1, 0), new Token(")", 1, 1), + new Token("{", 1, 2), new Token("}", 1, 3), + new Token("[", 1, 4), new Token("]", 1, 5), + new Token(";", 1, 6), new Token(",", 1, 7), + new Token(".", 1, 8))); + } + + /** + * <a href="http://java.sun.com/docs/books/jls/third_edition/html/lexical.html#3.12">Operators</a> + */ + @Test + public void shouldPreserveOperators() { + assertThat(chunk("+="), isTokens(new Token("+", 1, 0), new Token("=", 1, 1))); + assertThat(chunk("--"), isTokens(new Token("-", 1, 0), new Token("-", 1, 1))); + } + + @Test + public void realExamples() { + File testFile = DuplicationsTestUtil.findFile("/java/MessageResources.java"); + assertThat(chunker.chunk(testFile).size(), greaterThan(0)); + + testFile = DuplicationsTestUtil.findFile("/java/RequestUtils.java"); + assertThat(chunker.chunk(testFile).size(), greaterThan(0)); + } + + private static Matcher<List<Token>> isNumericLiteral() { + return isTokens(new Token("$NUMBER", 1, 0)); + } + + private static Matcher<List<Token>> isStringLiteral() { + return isTokens(new Token("$CHARS", 1, 0)); + } + + /** + * @return matcher for list of tokens + */ + private static Matcher<List<Token>> isTokens(Token... tokens) { + return is(Arrays.asList(tokens)); + } + + private List<Token> chunk(String sourceCode) { + return Lists.newArrayList(chunker.chunk(sourceCode)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/junit/TestNamePrinter.java b/sonar-duplications/src/test/java/org/sonar/duplications/junit/TestNamePrinter.java new file mode 100644 index 00000000000..bc7097f4b3b --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/junit/TestNamePrinter.java @@ -0,0 +1,32 @@ +/* + * 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.junit; + +import org.junit.rules.TestWatchman; +import org.junit.runners.model.FrameworkMethod; + +public class TestNamePrinter extends TestWatchman { + + @Override + public void starting(FrameworkMethod method) { + System.out.println("Executing " + method.getName()); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChannelDisptacherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChannelDisptacherTest.java new file mode 100644 index 00000000000..c7d7e53f770 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChannelDisptacherTest.java @@ -0,0 +1,70 @@ +/* + * 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.statement; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Matchers.any; +import static org.mockito.Matchers.anyListOf; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.times; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; +import static org.mockito.Mockito.when; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.statement.matcher.TokenMatcher; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class StatementChannelDisptacherTest { + + @Test(expected = IllegalStateException.class) + public void shouldThrowAnException() { + TokenMatcher tokenMatcher = mock(TokenMatcher.class); + StatementChannel channel = StatementChannel.create(tokenMatcher); + StatementChannelDisptacher dispatcher = new StatementChannelDisptacher(Arrays.asList(channel)); + TokenQueue tokenQueue = mock(TokenQueue.class); + when(tokenQueue.peek()).thenReturn(new Token("a", 1, 0)).thenReturn(null); + List<Statement> statements = mock(List.class); + + dispatcher.consume(tokenQueue, statements); + } + + @Test + public void shouldConsume() { + TokenMatcher tokenMatcher = mock(TokenMatcher.class); + when(tokenMatcher.matchToken(any(TokenQueue.class), anyListOf(Token.class))).thenReturn(true); + StatementChannel channel = StatementChannel.create(tokenMatcher); + StatementChannelDisptacher dispatcher = new StatementChannelDisptacher(Arrays.asList(channel)); + TokenQueue tokenQueue = mock(TokenQueue.class); + when(tokenQueue.peek()).thenReturn(new Token("a", 1, 0)).thenReturn(null); + List<Statement> statements = mock(List.class); + + assertThat(dispatcher.consume(tokenQueue, statements), is(true)); + verify(tokenQueue, times(2)).peek(); + verifyNoMoreInteractions(tokenQueue); + verifyNoMoreInteractions(statements); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChannelTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChannelTest.java new file mode 100644 index 00000000000..35ed1954fac --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChannelTest.java @@ -0,0 +1,101 @@ +/* + * 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.statement; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.mockito.ArgumentCaptor; +import org.mockito.Mockito; +import org.sonar.duplications.statement.matcher.AnyTokenMatcher; +import org.sonar.duplications.statement.matcher.TokenMatcher; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class StatementChannelTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNull() { + StatementChannel.create((TokenMatcher[]) null); + } + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptEmpty() { + StatementChannel.create(new TokenMatcher[] {}); + } + + @Test + public void shouldPushForward() { + TokenQueue tokenQueue = mock(TokenQueue.class); + TokenMatcher matcher = mock(TokenMatcher.class); + List<Statement> output = mock(List.class); + StatementChannel channel = StatementChannel.create(matcher); + + assertThat(channel.consume(tokenQueue, output), is(false)); + ArgumentCaptor<List> matchedTokenList = ArgumentCaptor.forClass(List.class); + verify(matcher).matchToken(Mockito.eq(tokenQueue), matchedTokenList.capture()); + verifyNoMoreInteractions(matcher); + verify(tokenQueue).pushForward(matchedTokenList.getValue()); + verifyNoMoreInteractions(tokenQueue); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldCreateStatement() { + Token token = new Token("a", 1, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(token))); + TokenMatcher matcher = spy(new AnyTokenMatcher()); + StatementChannel channel = StatementChannel.create(matcher); + List<Statement> output = mock(List.class); + + assertThat(channel.consume(tokenQueue, output), is(true)); + verify(matcher).matchToken(Mockito.eq(tokenQueue), Mockito.anyList()); + verifyNoMoreInteractions(matcher); + ArgumentCaptor<Statement> statement = ArgumentCaptor.forClass(Statement.class); + verify(output).add(statement.capture()); + assertThat(statement.getValue().getValue(), is("a")); + assertThat(statement.getValue().getStartLine(), is(1)); + assertThat(statement.getValue().getEndLine(), is(1)); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldNotCreateStatement() { + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(new Token("a", 1, 1)))); + TokenMatcher matcher = spy(new AnyTokenMatcher()); + StatementChannel channel = StatementChannel.create(matcher); + List<Statement> output = mock(List.class); + + assertThat(channel.consume(tokenQueue, output), is(true)); + verify(matcher).matchToken(Mockito.eq(tokenQueue), Mockito.anyList()); + verifyNoMoreInteractions(matcher); + verify(output).add(Mockito.any(Statement.class)); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChunkerTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChunkerTest.java new file mode 100644 index 00000000000..83b567abaff --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementChunkerTest.java @@ -0,0 +1,31 @@ +/* + * 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.statement; + +import org.junit.Test; + +public class StatementChunkerTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNull() { + StatementChunker.builder().build().chunk(null); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementTest.java new file mode 100644 index 00000000000..522b21f3496 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/StatementTest.java @@ -0,0 +1,51 @@ +/* + * 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.statement; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +import java.util.ArrayList; +import java.util.Arrays; + +import org.junit.Test; +import org.sonar.duplications.token.Token; + +public class StatementTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNull() { + new Statement(null); + } + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptEmpty() { + new Statement(new ArrayList<Token>()); + } + + @Test + public void shouldCreateStatementFromListOfTokens() { + Statement statement = new Statement(Arrays.asList(new Token("a", 1, 1), new Token("b", 2, 1))); + assertThat(statement.getValue(), is("ab")); + assertThat(statement.getStartLine(), is(1)); + assertThat(statement.getEndLine(), is(2)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/TokenMatcherFactoryTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/TokenMatcherFactoryTest.java new file mode 100644 index 00000000000..20be1e85869 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/TokenMatcherFactoryTest.java @@ -0,0 +1,48 @@ +/* + * 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.statement; + +import static org.hamcrest.Matchers.instanceOf; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; + +import org.junit.Test; +import org.sonar.duplications.statement.matcher.AnyTokenMatcher; +import org.sonar.duplications.statement.matcher.BridgeTokenMatcher; +import org.sonar.duplications.statement.matcher.ExactTokenMatcher; +import org.sonar.duplications.statement.matcher.ForgetLastTokenMatcher; +import org.sonar.duplications.statement.matcher.OptTokenMatcher; +import org.sonar.duplications.statement.matcher.TokenMatcher; +import org.sonar.duplications.statement.matcher.UptoTokenMatcher; + +public class TokenMatcherFactoryTest { + + @Test + public void shouldCreateMatchers() { + assertThat(TokenMatcherFactory.anyToken(), instanceOf(AnyTokenMatcher.class)); + assertThat(TokenMatcherFactory.bridge("(", ")"), instanceOf(BridgeTokenMatcher.class)); + assertThat(TokenMatcherFactory.forgetLastToken(), instanceOf(ForgetLastTokenMatcher.class)); + assertThat(TokenMatcherFactory.from("if"), instanceOf(ExactTokenMatcher.class)); + assertThat(TokenMatcherFactory.opt(mock(TokenMatcher.class)), instanceOf(OptTokenMatcher.class)); + assertThat(TokenMatcherFactory.to(";"), instanceOf(UptoTokenMatcher.class)); + assertThat(TokenMatcherFactory.token(";"), instanceOf(ExactTokenMatcher.class)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/AnyTokenMatcherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/AnyTokenMatcherTest.java new file mode 100644 index 00000000000..e607af5ce64 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/AnyTokenMatcherTest.java @@ -0,0 +1,53 @@ +/* + * 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.statement.matcher; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class AnyTokenMatcherTest { + + @Test + public void shouldMatch() { + Token t1 = new Token("a", 1, 1); + Token t2 = new Token("b", 2, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2))); + List<Token> output = mock(List.class); + AnyTokenMatcher matcher = new AnyTokenMatcher(); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verify(tokenQueue).poll(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/BridgeTokenMatcherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/BridgeTokenMatcherTest.java new file mode 100644 index 00000000000..2f73d4a55de --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/BridgeTokenMatcherTest.java @@ -0,0 +1,106 @@ +/* + * 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.statement.matcher; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.times; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class BridgeTokenMatcherTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNullAsLeft() { + new BridgeTokenMatcher(null, ")"); + } + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNullAsRight() { + new BridgeTokenMatcher("(", null); + } + + @Test + public void shouldMatch() { + Token t1 = new Token("(", 1, 1); + Token t2 = new Token("a", 2, 1); + Token t3 = new Token("(", 3, 1); + Token t4 = new Token("b", 4, 1); + Token t5 = new Token(")", 5, 1); + Token t6 = new Token("c", 6, 1); + Token t7 = new Token(")", 7, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2, t3, t4, t5, t6, t7))); + List<Token> output = mock(List.class); + BridgeTokenMatcher matcher = new BridgeTokenMatcher("(", ")"); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verify(tokenQueue, times(1)).isNextTokenValue("("); + verify(tokenQueue, times(7)).poll(); + verify(tokenQueue, times(7)).peek(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verify(output).add(t2); + verify(output).add(t3); + verify(output).add(t4); + verify(output).add(t5); + verify(output).add(t6); + verify(output).add(t7); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldNotMatchWhenNoLeft() { + Token t1 = new Token("a", 1, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1))); + List<Token> output = mock(List.class); + BridgeTokenMatcher matcher = new BridgeTokenMatcher("(", ")"); + + assertThat(matcher.matchToken(tokenQueue, output), is(false)); + verify(tokenQueue).isNextTokenValue("("); + verifyNoMoreInteractions(tokenQueue); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldNotMatchWhenNoRight() { + Token t1 = new Token("(", 1, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1))); + List<Token> output = mock(List.class); + BridgeTokenMatcher matcher = new BridgeTokenMatcher("(", ")"); + + assertThat(matcher.matchToken(tokenQueue, output), is(false)); + verify(tokenQueue, times(1)).isNextTokenValue("("); + verify(tokenQueue, times(1)).poll(); + verify(tokenQueue, times(2)).peek(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/ExactTokenMatcherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/ExactTokenMatcherTest.java new file mode 100644 index 00000000000..925d1d9ca63 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/ExactTokenMatcherTest.java @@ -0,0 +1,73 @@ +/* + * 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.statement.matcher; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class ExactTokenMatcherTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNull() { + new ExactTokenMatcher(null); + } + + @Test + public void shouldMatch() { + Token t1 = new Token("a", 1, 1); + Token t2 = new Token("b", 2, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2))); + List<Token> output = mock(List.class); + ExactTokenMatcher matcher = new ExactTokenMatcher("a"); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verify(tokenQueue).isNextTokenValue("a"); + verify(tokenQueue).poll(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldNotMatch() { + Token t1 = new Token("a", 1, 1); + Token t2 = new Token("b", 2, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2))); + List<Token> output = mock(List.class); + ExactTokenMatcher matcher = new ExactTokenMatcher("b"); + + assertThat(matcher.matchToken(tokenQueue, output), is(false)); + verify(tokenQueue).isNextTokenValue("b"); + verifyNoMoreInteractions(tokenQueue); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/ForgetLastTokenMatcherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/ForgetLastTokenMatcherTest.java new file mode 100644 index 00000000000..1050e7a10a3 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/ForgetLastTokenMatcherTest.java @@ -0,0 +1,52 @@ +/* + * 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.statement.matcher; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; +import static org.mockito.Mockito.when; + +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class ForgetLastTokenMatcherTest { + + @Test + public void shouldMatch() { + TokenQueue tokenQueue = spy(new TokenQueue()); + List<Token> output = mock(List.class); + when(output.size()).thenReturn(4); + ForgetLastTokenMatcher matcher = new ForgetLastTokenMatcher(); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verifyNoMoreInteractions(tokenQueue); + verify(output).size(); + verify(output).remove(3); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/OptTokenMatcherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/OptTokenMatcherTest.java new file mode 100644 index 00000000000..acddf6df379 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/OptTokenMatcherTest.java @@ -0,0 +1,56 @@ +/* + * 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.statement.matcher; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class OptTokenMatcherTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNull() { + new OptTokenMatcher(null); + } + + @Test + public void shouldMatch() { + TokenQueue tokenQueue = spy(new TokenQueue()); + TokenMatcher delegate = mock(TokenMatcher.class); + OptTokenMatcher matcher = new OptTokenMatcher(delegate); + List<Token> output = mock(List.class); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verify(delegate).matchToken(tokenQueue, output); + verifyNoMoreInteractions(delegate); + verifyNoMoreInteractions(tokenQueue); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/UptoTokenMatcherTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/UptoTokenMatcherTest.java new file mode 100644 index 00000000000..917c3948043 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/statement/matcher/UptoTokenMatcherTest.java @@ -0,0 +1,106 @@ +/* + * 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.statement.matcher; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.spy; +import static org.mockito.Mockito.times; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Test; +import org.sonar.duplications.token.Token; +import org.sonar.duplications.token.TokenQueue; + +public class UptoTokenMatcherTest { + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptNull() { + new UptoTokenMatcher(null); + } + + @Test(expected = IllegalArgumentException.class) + public void shouldNotAcceptEmpty() { + new UptoTokenMatcher(new String[] {}); + } + + @Test + public void shouldMatch() { + Token t1 = new Token("a", 1, 1); + Token t2 = new Token(";", 2, 1); // should stop on this token + Token t3 = new Token(";", 3, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2, t3))); + List<Token> output = mock(List.class); + UptoTokenMatcher matcher = new UptoTokenMatcher(new String[] { ";" }); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verify(tokenQueue, times(2)).poll(); + verify(tokenQueue).peek(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verify(output).add(t2); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldMatchAnyOfProvidedTokens() { + Token t1 = new Token("a", 1, 1); + Token t2 = new Token("{", 2, 1); + Token t3 = new Token("b", 3, 1); + Token t4 = new Token("}", 4, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2, t3, t4))); + List<Token> output = mock(List.class); + UptoTokenMatcher matcher = new UptoTokenMatcher(new String[] { "{", "}" }); + + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + assertThat(matcher.matchToken(tokenQueue, output), is(true)); + verify(tokenQueue, times(4)).poll(); + verify(tokenQueue, times(2)).peek(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verify(output).add(t2); + verify(output).add(t3); + verify(output).add(t4); + verifyNoMoreInteractions(output); + } + + @Test + public void shouldNotMatch() { + Token t1 = new Token("a", 1, 1); + Token t2 = new Token("b", 2, 1); + TokenQueue tokenQueue = spy(new TokenQueue(Arrays.asList(t1, t2))); + List<Token> output = mock(List.class); + UptoTokenMatcher matcher = new UptoTokenMatcher(new String[] { ";" }); + + assertThat(matcher.matchToken(tokenQueue, output), is(false)); + verify(tokenQueue, times(2)).poll(); + verify(tokenQueue, times(2)).peek(); + verifyNoMoreInteractions(tokenQueue); + verify(output).add(t1); + verify(output).add(t2); + verifyNoMoreInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/token/BlackHoleTokenChannelTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/token/BlackHoleTokenChannelTest.java new file mode 100644 index 00000000000..7f540256541 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/token/BlackHoleTokenChannelTest.java @@ -0,0 +1,44 @@ +/* + * 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.token; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.verifyZeroInteractions; + +import org.junit.Test; +import org.sonar.channel.CodeReader; + +public class BlackHoleTokenChannelTest { + + @Test + public void shouldConsume() { + BlackHoleTokenChannel channel = new BlackHoleTokenChannel("ABC"); + TokenQueue output = mock(TokenQueue.class); + CodeReader codeReader = new CodeReader("ABCD"); + + assertThat(channel.consume(codeReader, output), is(true)); + assertThat(codeReader.getLinePosition(), is(1)); + assertThat(codeReader.getColumnPosition(), is(3)); + verifyZeroInteractions(output); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenChannelTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenChannelTest.java new file mode 100644 index 00000000000..17baea189b9 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenChannelTest.java @@ -0,0 +1,92 @@ +/* + * 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.token; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.verify; +import static org.mockito.Mockito.verifyNoMoreInteractions; +import static org.mockito.Mockito.verifyZeroInteractions; + +import org.junit.Test; +import org.mockito.ArgumentCaptor; +import org.sonar.channel.CodeReader; + +public class TokenChannelTest { + + @Test + public void shouldConsume() { + TokenChannel channel = new TokenChannel("ABC"); + TokenQueue output = mock(TokenQueue.class); + CodeReader codeReader = new CodeReader("ABCD"); + + assertThat(channel.consume(codeReader, output), is(true)); + ArgumentCaptor<Token> token = ArgumentCaptor.forClass(Token.class); + verify(output).add(token.capture()); + assertThat(token.getValue(), is(new Token("ABC", 1, 0))); + verifyNoMoreInteractions(output); + assertThat(codeReader.getLinePosition(), is(1)); + assertThat(codeReader.getColumnPosition(), is(3)); + } + + @Test + public void shouldNormalize() { + TokenChannel channel = new TokenChannel("ABC", "normalized"); + TokenQueue output = mock(TokenQueue.class); + CodeReader codeReader = new CodeReader("ABCD"); + + assertThat(channel.consume(codeReader, output), is(true)); + ArgumentCaptor<Token> token = ArgumentCaptor.forClass(Token.class); + verify(output).add(token.capture()); + assertThat(token.getValue(), is(new Token("normalized", 1, 0))); + verifyNoMoreInteractions(output); + assertThat(codeReader.getLinePosition(), is(1)); + assertThat(codeReader.getColumnPosition(), is(3)); + } + + @Test + public void shouldNotConsume() { + TokenChannel channel = new TokenChannel("ABC"); + TokenQueue output = mock(TokenQueue.class); + CodeReader codeReader = new CodeReader("123"); + + assertThat(channel.consume(new CodeReader("123"), output), is(false)); + verifyZeroInteractions(output); + assertThat(codeReader.getLinePosition(), is(1)); + assertThat(codeReader.getColumnPosition(), is(0)); + } + + @Test + public void shouldCorrectlyDeterminePositionWhenTokenSpansMultipleLines() { + TokenChannel channel = new TokenChannel("AB\nC"); + TokenQueue output = mock(TokenQueue.class); + CodeReader codeReader = new CodeReader("AB\nCD"); + + assertThat(channel.consume(codeReader, output), is(true)); + ArgumentCaptor<Token> token = ArgumentCaptor.forClass(Token.class); + verify(output).add(token.capture()); + assertThat(token.getValue(), is(new Token("AB\nC", 1, 0))); + verifyNoMoreInteractions(output); + assertThat(codeReader.getLinePosition(), is(2)); + assertThat(codeReader.getColumnPosition(), is(1)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenChunkerTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenChunkerTest.java new file mode 100644 index 00000000000..d9a421ac4d0 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenChunkerTest.java @@ -0,0 +1,46 @@ +/* + * 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.token; + +import org.junit.Test; + +public class TokenChunkerTest { + + /** + * In fact this test does not guarantee that we will be able to consume even more great comments, + * because {@link org.sonar.channel.CodeBuffer} does not expand dynamically - see issue SONAR-2632. + * But at least guarantees that we able to consume source files from JDK 1.6, + * because buffer capacity has been increased in comparison with default value, + * which is {@link org.sonar.channel.CodeReaderConfiguration#DEFAULT_BUFFER_CAPACITY}. + */ + @Test(timeout = 5000) + public void shouldConsumeBigComments() { + int capacity = 80000; + StringBuilder sb = new StringBuilder(capacity); + sb.append("/"); + for (int i = 3; i < capacity; i++) { + sb.append('*'); + } + sb.append("/"); + TokenChunker chunker = TokenChunker.builder().token("/.*/", "LITERAL").build(); + chunker.chunk(sb.toString()); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenQueueTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenQueueTest.java new file mode 100644 index 00000000000..bdb6ba00c58 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenQueueTest.java @@ -0,0 +1,68 @@ +/* + * 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.token; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +import java.util.ArrayList; +import java.util.List; + +import org.junit.Before; +import org.junit.Test; + +public class TokenQueueTest { + + TokenQueue tokenQueue; + + @Before + public void initTest() { + List<Token> tokenList = new ArrayList<Token>(); + tokenList.add(new Token("a", 1, 0)); + tokenList.add(new Token("bc", 1, 2)); + tokenList.add(new Token("def", 1, 5)); + tokenQueue = new TokenQueue(tokenList); + } + + @Test + public void shouldPeekToken() { + Token token = tokenQueue.peek(); + assertThat(token, is(new Token("a", 1, 0))); + assertThat(tokenQueue.size(), is(3)); + } + + @Test + public void shouldPollToken() { + Token token = tokenQueue.poll(); + assertThat(token, is(new Token("a", 1, 0))); + assertThat(tokenQueue.size(), is(2)); + } + + @Test + public void shouldPushTokenAtBegining() { + Token pushedToken = new Token("push", 1, 0); + List<Token> pushedTokenList = new ArrayList<Token>(); + pushedTokenList.add(pushedToken); + tokenQueue.pushForward(pushedTokenList); + assertThat(tokenQueue.peek(), is(pushedToken)); + assertThat(tokenQueue.size(), is(4)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenTest.java new file mode 100644 index 00000000000..9e4e7785d19 --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/token/TokenTest.java @@ -0,0 +1,49 @@ +/* + * 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.token; + +import org.junit.Test; + +import static org.junit.Assert.assertThat; + +import static org.hamcrest.Matchers.is; +import static org.hamcrest.Matchers.not; + +public class TokenTest { + + @Test + public void shouldBeEqual() { + Token firstToken = new Token("MyValue", 1, 3); + Token secondToken = new Token("MyValue", 1, 3); + + assertThat(firstToken, is(secondToken)); + } + + @Test + public void shouldNotBeEqual() { + Token firstToken = new Token("MyValue", 1, 3); + Token secondToken = new Token("MySecondValue", 1, 3); + Token thirdToken = new Token("MyValue", 3, 3); + + assertThat(firstToken, not(is(secondToken))); + assertThat(firstToken, not(is(thirdToken))); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/utils/FastStringComparatorTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/utils/FastStringComparatorTest.java new file mode 100644 index 00000000000..ddc050ce2bc --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/utils/FastStringComparatorTest.java @@ -0,0 +1,70 @@ +/* + * 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.utils; + +import static org.hamcrest.Matchers.greaterThan; +import static org.hamcrest.Matchers.is; +import static org.hamcrest.Matchers.lessThan; +import static org.junit.Assert.assertThat; +import static org.junit.Assert.assertTrue; + +import org.junit.Test; +import org.sonar.duplications.utils.FastStringComparator; + +public class FastStringComparatorTest { + + @Test + public void sameHashCode() { + // Next two Strings have same hash code in Java - see http://www.drmaciver.com/2008/07/javalangstringhashcode/ + String s1 = "Od"; + String s2 = "PE"; + assertTrue("same hash code", s1.hashCode() == s2.hashCode()); + assertThat("s1 < s2", FastStringComparator.INSTANCE.compare(s1, s2), lessThan(0)); + assertThat("s2 > s1", FastStringComparator.INSTANCE.compare(s2, s1), greaterThan(0)); + } + + @Test + public void differentHashCode() { + String s1 = "a"; + String s2 = "c"; + assertTrue("different hash code", s1.hashCode() != s2.hashCode()); + assertThat("s1 < s2", FastStringComparator.INSTANCE.compare(s1, s2), is(-1)); + assertThat("s2 > s1", FastStringComparator.INSTANCE.compare(s2, s1), is(1)); + } + + @Test + public void sameObject() { + String s1 = "a"; + String s2 = s1; + assertTrue("same objects", s1 == s2); + assertThat("s1 = s2", FastStringComparator.INSTANCE.compare(s1, s2), is(0)); + assertThat("s2 = s1", FastStringComparator.INSTANCE.compare(s2, s1), is(0)); + } + + @Test + public void sameString() { + String s1 = new String("a"); + String s2 = new String("a"); + assertTrue("different objects", s1 != s2); + assertThat("s1 = s2", FastStringComparator.INSTANCE.compare(s1, s2), is(0)); + assertThat("s2 = s1", FastStringComparator.INSTANCE.compare(s2, s1), is(0)); + } + +} diff --git a/sonar-duplications/src/test/java/org/sonar/duplications/utils/SortedListsUtilsTest.java b/sonar-duplications/src/test/java/org/sonar/duplications/utils/SortedListsUtilsTest.java new file mode 100644 index 00000000000..cf099af6eab --- /dev/null +++ b/sonar-duplications/src/test/java/org/sonar/duplications/utils/SortedListsUtilsTest.java @@ -0,0 +1,60 @@ +/* + * 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.utils; + +import static org.hamcrest.Matchers.is; +import static org.junit.Assert.assertThat; + +import java.util.Arrays; +import java.util.Comparator; +import java.util.List; + +import org.junit.Test; + +public class SortedListsUtilsTest { + + @Test + public void testContains() { + List<Integer> c1 = Arrays.asList(1, 2, 3); + List<Integer> c2 = Arrays.asList(1, 2); + List<Integer> c3 = Arrays.asList(1, 3); + + assertThat(SortedListsUtils.contains(c1, c1, IntegerComparator.INSTANCE), is(true)); + assertThat(SortedListsUtils.contains(c1, c2, IntegerComparator.INSTANCE), is(true)); + assertThat(SortedListsUtils.contains(c1, c3, IntegerComparator.INSTANCE), is(true)); + + assertThat(SortedListsUtils.contains(c2, c1, IntegerComparator.INSTANCE), is(false)); + assertThat(SortedListsUtils.contains(c2, c2, IntegerComparator.INSTANCE), is(true)); + assertThat(SortedListsUtils.contains(c2, c3, IntegerComparator.INSTANCE), is(false)); + + assertThat(SortedListsUtils.contains(c3, c1, IntegerComparator.INSTANCE), is(false)); + assertThat(SortedListsUtils.contains(c3, c2, IntegerComparator.INSTANCE), is(false)); + assertThat(SortedListsUtils.contains(c3, c3, IntegerComparator.INSTANCE), is(true)); + } + + private static class IntegerComparator implements Comparator<Integer> { + public static final IntegerComparator INSTANCE = new IntegerComparator(); + + public int compare(Integer o1, Integer o2) { + return o1 - o2; + } + } + +} |