diff options
Diffstat (limited to 'sonar-duplications/src/main')
38 files changed, 3177 insertions, 0 deletions
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() { + } + +} |