From 1c0e443d98bc85f3f2d7e422d84c0b2df10b2906 Mon Sep 17 00:00:00 2001 From: =?utf8?q?S=C3=A9bastien=20Lesaint?= Date: Mon, 30 May 2016 15:28:54 +0200 Subject: [PATCH] SONAR-3321 add step detecting file moves --- ...ReportComputeEngineContainerPopulator.java | 8 + .../filemove/FileMoveDetectionStep.java | 433 ++++++++++++++++ .../computation/filemove/FileSimilarity.java | 57 +++ .../filemove/FileSimilarityImpl.java | 45 ++ .../filemove/MovedFilesRepository.java | 86 ++++ .../filemove/MutableMovedFilesRepository.java | 34 ++ .../MutableMovedFilesRepositoryImpl.java | 57 +++ .../filemove/SourceSimilarity.java | 30 ++ .../filemove/SourceSimilarityImpl.java | 82 +++ .../computation/filemove/package-info.java | 24 + .../step/ReportComputationSteps.java | 2 + .../filemove/FileMoveDetectionStepTest.java | 483 ++++++++++++++++++ .../MutableMovedFilesRepositoryImplTest.java | 140 +++++ .../MutableMovedFilesRepositoryRule.java | 60 +++ .../filemove/SourceSimilarityImplTest.java | 56 ++ 15 files changed, 1597 insertions(+) create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileMoveDetectionStep.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarity.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarityImpl.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MovedFilesRepository.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepository.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImpl.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarity.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarityImpl.java create mode 100644 server/sonar-server/src/main/java/org/sonar/server/computation/filemove/package-info.java create mode 100644 server/sonar-server/src/test/java/org/sonar/server/computation/filemove/FileMoveDetectionStepTest.java create mode 100644 server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImplTest.java create mode 100644 server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryRule.java create mode 100644 server/sonar-server/src/test/java/org/sonar/server/computation/filemove/SourceSimilarityImplTest.java diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/container/ReportComputeEngineContainerPopulator.java b/server/sonar-server/src/main/java/org/sonar/server/computation/container/ReportComputeEngineContainerPopulator.java index b0e9666e7ef..b79ff4bdc7e 100644 --- a/server/sonar-server/src/main/java/org/sonar/server/computation/container/ReportComputeEngineContainerPopulator.java +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/container/ReportComputeEngineContainerPopulator.java @@ -37,6 +37,9 @@ import org.sonar.server.computation.duplication.CrossProjectDuplicationStatusHol import org.sonar.server.computation.duplication.DuplicationRepositoryImpl; import org.sonar.server.computation.duplication.IntegrateCrossProjectDuplications; import org.sonar.server.computation.event.EventRepositoryImpl; +import org.sonar.server.computation.filemove.FileSimilarityImpl; +import org.sonar.server.computation.filemove.MutableMovedFilesRepositoryImpl; +import org.sonar.server.computation.filemove.SourceSimilarityImpl; import org.sonar.server.computation.filesystem.ComputationTempFolderProvider; import org.sonar.server.computation.issue.BaseIssuesLoader; import org.sonar.server.computation.issue.CloseIssuesOnRemovedComponentsVisitor; @@ -211,6 +214,11 @@ public final class ReportComputeEngineContainerPopulator implements ContainerPop TrackerExecution.class, BaseIssuesLoader.class, + // filemove + SourceSimilarityImpl.class, + FileSimilarityImpl.class, + MutableMovedFilesRepositoryImpl.class, + // duplication IntegrateCrossProjectDuplications.class, diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileMoveDetectionStep.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileMoveDetectionStep.java new file mode 100644 index 00000000000..dc305b3f8db --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileMoveDetectionStep.java @@ -0,0 +1,433 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import com.google.common.base.Predicate; +import com.google.common.collect.ArrayListMultimap; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Multimap; +import com.google.common.collect.Sets; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.Set; +import javax.annotation.Nonnull; +import javax.annotation.Nullable; +import javax.annotation.concurrent.Immutable; +import org.sonar.api.resources.Qualifiers; +import org.sonar.api.utils.log.Logger; +import org.sonar.api.utils.log.Loggers; +import org.sonar.core.hash.SourceHashComputer; +import org.sonar.core.hash.SourceLinesHashesComputer; +import org.sonar.core.util.CloseableIterator; +import org.sonar.db.DbClient; +import org.sonar.db.DbSession; +import org.sonar.db.component.ComponentDtoFunctions; +import org.sonar.db.component.ComponentDtoWithSnapshotId; +import org.sonar.db.component.ComponentTreeQuery; +import org.sonar.db.component.SnapshotDto; +import org.sonar.db.source.FileSourceDto; +import org.sonar.server.computation.analysis.AnalysisMetadataHolder; +import org.sonar.server.computation.component.Component; +import org.sonar.server.computation.component.CrawlerDepthLimit; +import org.sonar.server.computation.component.DepthTraversalTypeAwareCrawler; +import org.sonar.server.computation.component.TreeRootHolder; +import org.sonar.server.computation.component.TypeAwareVisitorAdapter; +import org.sonar.server.computation.snapshot.Snapshot; +import org.sonar.server.computation.source.SourceLinesRepository; +import org.sonar.server.computation.step.ComputationStep; + +import static com.google.common.base.Splitter.on; +import static com.google.common.collect.FluentIterable.from; +import static java.lang.Math.max; +import static java.util.Arrays.asList; +import static java.util.Collections.singletonList; +import static org.sonar.server.computation.component.ComponentVisitor.Order.POST_ORDER; + +public class FileMoveDetectionStep implements ComputationStep { + private static final Logger LOG = Loggers.get(FileMoveDetectionStep.class); + private static final int MIN_REQUIRED_SCORE = 90; + + private final AnalysisMetadataHolder analysisMetadataHolder; + private final TreeRootHolder rootHolder; + private final DbClient dbClient; + private final SourceLinesRepository sourceLinesRepository; + private final FileSimilarity fileSimilarity; + private final MutableMovedFilesRepository movedFilesRepository; + + public FileMoveDetectionStep(AnalysisMetadataHolder analysisMetadataHolder, TreeRootHolder rootHolder, DbClient dbClient, + SourceLinesRepository sourceLinesRepository, FileSimilarity fileSimilarity, MutableMovedFilesRepository movedFilesRepository) { + this.analysisMetadataHolder = analysisMetadataHolder; + this.rootHolder = rootHolder; + this.dbClient = dbClient; + this.sourceLinesRepository = sourceLinesRepository; + this.fileSimilarity = fileSimilarity; + this.movedFilesRepository = movedFilesRepository; + } + + @Override + public String getDescription() { + return "Detect file moves"; + } + + @Override + public void execute() { + // do nothing if no files in db (first analysis) + Snapshot baseProjectSnapshot = analysisMetadataHolder.getBaseProjectSnapshot(); + if (baseProjectSnapshot == null) { + LOG.trace("First analysis. Do nothing."); + return; + } + + Map dbFilesByKey = getDbFilesByKey(baseProjectSnapshot); + + if (dbFilesByKey.isEmpty()) { + LOG.trace("Previous snapshot has no file. Do nothing."); + return; + } + + Map reportFilesByKey = getReportFilesByKey(this.rootHolder.getRoot()); + + if (reportFilesByKey.isEmpty()) { + LOG.trace("No File in report. Do nothing."); + return; + } + + Set addedFileKeys = ImmutableSet.copyOf(Sets.difference(reportFilesByKey.keySet(), dbFilesByKey.keySet())); + Set removedFileKeys = ImmutableSet.copyOf(Sets.difference(dbFilesByKey.keySet(), reportFilesByKey.keySet())); + + // can find matches if at least one of the added or removed files groups is empty => abort + if (addedFileKeys.isEmpty() || removedFileKeys.isEmpty()) { + LOG.trace("No file added nor removed. Do nothing."); + return; + } + + // retrieve file data from db and report + Map dbFileSourcesByKey = getDbFileSourcesByKey(dbFilesByKey, removedFileKeys); + Map reportFileSourcesByKey = getReportFileSourcesByKey(reportFilesByKey, addedFileKeys); + + // compute score matrix + ScoreMatrix scoreMatrix = computeScoreMatrix(dbFileSourcesByKey, reportFileSourcesByKey); + + // not a single match with score higher than MIN_REQUIRED_SCORE => abort + if (scoreMatrix.isEmpty()) { + return; + } + + MatchesByScore matchesByScore = MatchesByScore.create(scoreMatrix); + + ElectedMatches electedMatches = electMatches(dbFileSourcesByKey, reportFileSourcesByKey, matchesByScore); + + for (Match validatedMatch : electedMatches) { + movedFilesRepository.setOriginalFile( + reportFilesByKey.get(validatedMatch.getReportKey()), + toOriginalFile(dbFilesByKey.get(validatedMatch.getDbKey()))); + LOG.info("match found: " + validatedMatch); + } + } + + private Map getDbFilesByKey(Snapshot baseProjectSnapshot) { + try (DbSession dbSession = dbClient.openSession(false)) { + return from(dbClient.componentDao().selectAllChildren( + dbSession, + ComponentTreeQuery.builder() + .setBaseSnapshot(new SnapshotDto() + .setId(baseProjectSnapshot.getId()) + .setRootId(baseProjectSnapshot.getId())) + .setQualifiers(asList(Qualifiers.FILE, Qualifiers.UNIT_TEST_FILE)) + .setSortFields(singletonList("name")) + .setPageSize(Integer.MAX_VALUE) + .setPage(1) + .build())) + .uniqueIndex(ComponentDtoFunctions.toKey()); + } + } + + private static Map getReportFilesByKey(Component root) { + final ImmutableMap.Builder builder = ImmutableMap.builder(); + new DepthTraversalTypeAwareCrawler( + new TypeAwareVisitorAdapter(CrawlerDepthLimit.FILE, POST_ORDER) { + @Override + public void visitFile(Component file) { + builder.put(file.getKey(), file); + } + }).visit(root); + return builder.build(); + } + + private Map getDbFileSourcesByKey(Map dbFilesByKey, Set removedFileKeys) { + try (DbSession dbSession = dbClient.openSession(false)) { + ImmutableMap.Builder builder = ImmutableMap.builder(); + for (String fileKey : removedFileKeys) { + ComponentDtoWithSnapshotId componentDto = dbFilesByKey.get(fileKey); + FileSourceDto fileSourceDto = dbClient.fileSourceDao().selectSourceByFileUuid(dbSession, componentDto.uuid()); + if (fileSourceDto != null) { + builder.put(fileKey, new FileSimilarity.File(componentDto.path(), fileSourceDto.getSrcHash(), on('\n').splitToList(fileSourceDto.getLineHashes()))); + } + } + return builder.build(); + } + } + + private Map getReportFileSourcesByKey(Map reportFilesByKey, Set addedFileKeys) { + ImmutableMap.Builder builder = ImmutableMap.builder(); + for (String fileKey : addedFileKeys) { + // FIXME computation of sourceHash and lineHashes might be done multiple times for some files: here, in ComputeFileSourceData, in + // SourceHashRepository + Component component = reportFilesByKey.get(fileKey); + SourceLinesHashesComputer linesHashesComputer = new SourceLinesHashesComputer(); + SourceHashComputer sourceHashComputer = new SourceHashComputer(); + try (CloseableIterator lineIterator = sourceLinesRepository.readLines(component)) { + while (lineIterator.hasNext()) { + String line = lineIterator.next(); + linesHashesComputer.addLine(line); + sourceHashComputer.addLine(line, lineIterator.hasNext()); + } + } + builder.put(fileKey, new FileSimilarity.File(component.getReportAttributes().getPath(), sourceHashComputer.getHash(), linesHashesComputer.getLineHashes())); + } + return builder.build(); + } + + private ScoreMatrix computeScoreMatrix(Map dbFileSourcesByKey, Map reportFileSourcesByKey) { + int[][] scoreMatrix = new int[dbFileSourcesByKey.size()][reportFileSourcesByKey.size()]; + int maxScore = 0; + + int dbFileIndex = 0; + for (Map.Entry dbFileSourceAndKey : dbFileSourcesByKey.entrySet()) { + FileSimilarity.File fileInDb = dbFileSourceAndKey.getValue(); + int reportFileIndex = 0; + for (Map.Entry reportFileSourceAndKey : reportFileSourcesByKey.entrySet()) { + FileSimilarity.File unmatchedFile = reportFileSourceAndKey.getValue(); + int score = fileSimilarity.score(fileInDb, unmatchedFile); + scoreMatrix[dbFileIndex][reportFileIndex] = score; + if (score > maxScore) { + maxScore = score; + } + reportFileIndex++; + } + dbFileIndex++; + } + + return new ScoreMatrix(dbFileSourcesByKey, reportFileSourcesByKey, scoreMatrix, maxScore); + } + + private ElectedMatches electMatches(Map dbFileSourcesByKey, Map reportFileSourcesByKey, MatchesByScore matchesByScore) { + ElectedMatches electedMatches = new ElectedMatches(matchesByScore, dbFileSourcesByKey, reportFileSourcesByKey); + Multimap matchesPerFileForScore = ArrayListMultimap.create(); + for (List matches : matchesByScore) { + // no match for this score value, ignore + if (matches == null) { + continue; + } + + List matchesToValidate = electedMatches.filter(matches); + if (matches.isEmpty()) { + continue; + } + if (matches.size() == 1) { + Match match = matches.get(0); + electedMatches.add(match); + } else { + matchesPerFileForScore.clear(); + for (Match match : matches) { + matchesPerFileForScore.put(match.getDbKey(), match); + matchesPerFileForScore.put(match.getReportKey(), match); + } + // validate non ambiguous matches (ie. the match is the only match of either the db file and the report file) + for (Match match : matchesToValidate) { + int dbFileMatchesCount = matchesPerFileForScore.get(match.getDbKey()).size(); + int reportFileMatchesCount = matchesPerFileForScore.get(match.getReportKey()).size(); + if (dbFileMatchesCount == 1 && reportFileMatchesCount == 1) { + electedMatches.add(match); + } + } + } + } + return electedMatches; + } + + private static MovedFilesRepository.OriginalFile toOriginalFile(ComponentDtoWithSnapshotId componentDto) { + return new MovedFilesRepository.OriginalFile(componentDto.getId(), componentDto.uuid(), componentDto.getKey()); + } + + private static final class ScoreMatrix { + private final Map dbFileSourcesByKey; + private final Map reportFileSourcesByKey; + private final int[][] scores; + private final int maxScore; + + public ScoreMatrix(Map dbFileSourcesByKey, Map reportFileSourcesByKey, + int[][] scores, int maxScore) { + this.dbFileSourcesByKey = dbFileSourcesByKey; + this.reportFileSourcesByKey = reportFileSourcesByKey; + this.scores = scores; + this.maxScore = maxScore; + } + + public void accept(ScoreMatrixVisitor visitor) { + int dbFileIndex = 0; + for (Map.Entry dbFileSourceAndKey : dbFileSourcesByKey.entrySet()) { + int reportFileIndex = 0; + for (Map.Entry reportFileSourceAndKey : reportFileSourcesByKey.entrySet()) { + int score = scores[dbFileIndex][reportFileIndex]; + visitor.visit(dbFileSourceAndKey.getKey(), reportFileSourceAndKey.getKey(), score); + reportFileIndex++; + } + dbFileIndex++; + } + } + + public boolean isEmpty() { + return maxScore == 0; + } + + private interface ScoreMatrixVisitor { + void visit(String dbFileKey, String reportFileKey, int score); + } + } + + @Immutable + private static final class Match { + private final String dbKey; + private final String reportKey; + + public Match(String dbKey, String reportKey) { + this.dbKey = dbKey; + this.reportKey = reportKey; + } + + public String getDbKey() { + return dbKey; + } + + public String getReportKey() { + return reportKey; + } + + @Override + public boolean equals(@Nullable Object o) { + if (this == o) { + return true; + } + if (o == null || getClass() != o.getClass()) { + return false; + } + Match match = (Match) o; + return dbKey.equals(match.dbKey) && reportKey.equals(match.reportKey); + } + + @Override + public int hashCode() { + return Objects.hash(dbKey, reportKey); + } + + @Override + public String toString() { + return '{' + dbKey + "=>" + reportKey + '}'; + } + } + + private static class MatchesByScore implements ScoreMatrix.ScoreMatrixVisitor, Iterable> { + private final ScoreMatrix scoreMatrix; + private List[] matches; + private int totalMatches = 0; + + private MatchesByScore(ScoreMatrix scoreMatrix) { + this.scoreMatrix = scoreMatrix; + this.matches = new List[max(MIN_REQUIRED_SCORE, scoreMatrix.maxScore) - MIN_REQUIRED_SCORE]; + } + + public static MatchesByScore create(ScoreMatrix scoreMatrix) { + MatchesByScore res = new MatchesByScore(scoreMatrix); + res.populate(); + return res; + } + + private void populate() { + scoreMatrix.accept(this); + } + + @Override + public void visit(String dbFileKey, String reportFileKey, int score) { + if (!isAcceptableScore(score)) { + return; + } + + int index = score - MIN_REQUIRED_SCORE - 1; + if (matches[index] == null) { + matches[index] = new ArrayList<>(1); + } + Match match = new Match(dbFileKey, reportFileKey); + matches[index].add(match); + totalMatches++; + } + + public int getSize() { + return totalMatches; + } + + @Override + public Iterator> iterator() { + return Arrays.asList(matches).iterator(); + } + + private static boolean isAcceptableScore(int score) { + return score >= MIN_REQUIRED_SCORE; + } + } + + private static class ElectedMatches implements Iterable { + private final List matches; + private final Set matchedFileKeys; + private final Predicate notAlreadyMatched = new Predicate() { + @Override + public boolean apply(@Nonnull Match input) { + return !(matchedFileKeys.contains(input.getDbKey()) || matchedFileKeys.contains(input.getReportKey())); + } + }; + + public ElectedMatches(MatchesByScore matchesByScore, Map dbFileSourcesByKey, + Map reportFileSourcesByKey) { + this.matches = new ArrayList<>(matchesByScore.getSize()); + this.matchedFileKeys = new HashSet<>(dbFileSourcesByKey.size() + reportFileSourcesByKey.size()); + } + + public void add(Match match) { + matches.add(match); + matchedFileKeys.add(match.getDbKey()); + matchedFileKeys.add(match.getReportKey()); + } + + public List filter(Iterable matches) { + return from(matches).filter(notAlreadyMatched).toList(); + } + + @Override + public Iterator iterator() { + return matches.iterator(); + } + } +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarity.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarity.java new file mode 100644 index 00000000000..db137494f5f --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarity.java @@ -0,0 +1,57 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.List; +import javax.annotation.CheckForNull; +import javax.annotation.Nullable; + +import static java.util.Objects.requireNonNull; + +public interface FileSimilarity { + + final class File { + private final String path; + private final String srcHash; + private final List lineHashes; + + public File(String path, @Nullable String srcHash, @Nullable List lineHashes) { + this.path = requireNonNull(path, "path can not be null"); + this.srcHash = srcHash; + this.lineHashes = lineHashes; + } + + public String getPath() { + return path; + } + + @CheckForNull + public String getSrcHash() { + return srcHash; + } + + @CheckForNull + public List getLineHashes() { + return lineHashes; + } + } + + int score(File file1, File file2); +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarityImpl.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarityImpl.java new file mode 100644 index 00000000000..bf30897d490 --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/FileSimilarityImpl.java @@ -0,0 +1,45 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.List; + +public class FileSimilarityImpl implements FileSimilarity { + + private final SourceSimilarity sourceSimilarity; + + public FileSimilarityImpl(SourceSimilarity sourceSimilarity) { + this.sourceSimilarity = sourceSimilarity; + } + + @Override + public int score(File file1, File file2) { + int score = 0; + + // TODO check filenames + + List lineHashes1 = file1.getLineHashes(); + List lineHashes2 = file2.getLineHashes(); + if (lineHashes1 != null && lineHashes2 != null) { + score += sourceSimilarity.score(lineHashes1, lineHashes2); + } + return score; + } +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MovedFilesRepository.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MovedFilesRepository.java new file mode 100644 index 00000000000..3511054cdbd --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MovedFilesRepository.java @@ -0,0 +1,86 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import com.google.common.base.Optional; +import javax.annotation.Nullable; +import org.sonar.server.computation.component.Component; + +import static java.util.Objects.requireNonNull; + +public interface MovedFilesRepository { + /** + * The original file for the specified component if it was registered as a moved file in the repository. + *

+ * Calling this method with a Component which is not a file, will always return {@link Optional#absent()}. + *

+ */ + Optional getOriginalFile(Component file); + + final class OriginalFile { + private final long id; + private final String uuid; + private final String key; + + public OriginalFile(long id, String uuid, String key) { + this.id = id; + this.uuid = requireNonNull(uuid, "uuid can not be null"); + this.key = requireNonNull(key, "key can not be null"); + } + + public long getId() { + return id; + } + + public String getUuid() { + return uuid; + } + + public String getKey() { + return key; + } + + @Override + public boolean equals(@Nullable Object o) { + if (this == o) { + return true; + } + if (o == null || getClass() != o.getClass()) { + return false; + } + OriginalFile that = (OriginalFile) o; + return uuid.equals(that.uuid); + } + + @Override + public int hashCode() { + return uuid.hashCode(); + } + + @Override + public String toString() { + return "OriginalFile{" + + "id=" + id + + ", uuid='" + uuid + '\'' + + ", key='" + key + '\'' + + '}'; + } + } +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepository.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepository.java new file mode 100644 index 00000000000..0eee9fa4e22 --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepository.java @@ -0,0 +1,34 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import org.sonar.server.computation.component.Component; + +import static org.sonar.server.computation.component.Component.Type; + +public interface MutableMovedFilesRepository extends MovedFilesRepository { + /** + * Registers the original file for the specified file of the report. + * + * @throws IllegalArgumentException if {@code file} type is not {@link Type#FILE} + * @throws IllegalStateException if {@code file} already has an original file + */ + void setOriginalFile(Component file, OriginalFile originalFile); +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImpl.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImpl.java new file mode 100644 index 00000000000..bb09fa17f30 --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImpl.java @@ -0,0 +1,57 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import com.google.common.base.Optional; +import java.util.HashMap; +import java.util.Map; +import org.sonar.server.computation.component.Component; + +import static com.google.common.base.Preconditions.checkArgument; +import static com.google.common.base.Preconditions.checkState; +import static java.util.Objects.requireNonNull; + +public class MutableMovedFilesRepositoryImpl implements MutableMovedFilesRepository { + private final Map originalFiles = new HashMap<>(); + + @Override + public void setOriginalFile(Component file, OriginalFile originalFile) { + requireNonNull(file, "file can't be null"); + requireNonNull(originalFile, "originalFile can't be null"); + checkArgument(file.getType() == Component.Type.FILE, "file must be of type FILE"); + + OriginalFile existingOriginalFile = originalFiles.get(file.getKey()); + checkState(existingOriginalFile == null || existingOriginalFile.equals(originalFile), + "Original file %s already registered for file %s", existingOriginalFile, file); + if (existingOriginalFile == null) { + originalFiles.put(file.getKey(), originalFile); + } + } + + @Override + public Optional getOriginalFile(Component file) { + requireNonNull(file, "file can't be null"); + if (file.getType() != Component.Type.FILE) { + return Optional.absent(); + } + + return Optional.fromNullable(originalFiles.get(file.getKey())); + } +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarity.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarity.java new file mode 100644 index 00000000000..a244f0f88cb --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarity.java @@ -0,0 +1,30 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.List; + +public interface SourceSimilarity { + + // TODO verify algorithm http://stackoverflow.com/questions/6087281/similarity-score-levenshtein + // the higher the more similar. Order is not important (TODO to be verified). 100% = same source. + // Range: between 0 and 100 (TODO to be verified) + int score(List left, List right); +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarityImpl.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarityImpl.java new file mode 100644 index 00000000000..c6b30bad3c6 --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/SourceSimilarityImpl.java @@ -0,0 +1,82 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.List; + +import static java.lang.Math.max; +import static java.lang.Math.min; + +// TODO evaluate https://commons.apache.org/sandbox/commons-text/jacoco/org.apache.commons.text.similarity/CosineSimilarity.java.html +// TODO another possible algorithm : just take the intersection of line hashes. That would allow to support block moving. +public class SourceSimilarityImpl implements SourceSimilarity { + + // TODO verify algorithm http://stackoverflow.com/questions/6087281/similarity-score-levenshtein + @Override + public int score(List left, List right) { + int distance = levenshteinDistance(left, right); + return (int) (100 * (1.0 - ((double) distance) / (max(left.size(), right.size())))); + } + + // TODO verify https://commons.apache.org/sandbox/commons-text/jacoco/org.apache.commons.text.similarity/LevenshteinDistance.java.html + int levenshteinDistance(List left, List right) { + int len0 = left.size() + 1; + int len1 = right.size() + 1; + + // the array of distances + int[] cost = new int[len0]; + int[] newcost = new int[len0]; + + // initial cost of skipping prefix in String s0 + for (int i = 0; i < len0; i++) { + cost[i] = i; + } + + // dynamically computing the array of distances + + // transformation cost for each letter in s1 + for (int j = 1; j < len1; j++) { + // initial cost of skipping prefix in String s1 + newcost[0] = j; + + // transformation cost for each letter in s0 + for (int i = 1; i < len0; i++) { + // matching current letters in both strings + int match = (left.get(i - 1).equals(right.get(j - 1))) ? 0 : 1; + + // computing cost for each transformation + int costReplace = cost[i - 1] + match; + int costInsert = cost[i] + 1; + int costDelete = newcost[i - 1] + 1; + + // keep minimum cost + newcost[i] = min(min(costInsert, costDelete), costReplace); + } + + // swap cost/newcost arrays + int[] swap = cost; + cost = newcost; + newcost = swap; + } + + // the distance is the cost for transforming all letters in both strings + return cost[len0 - 1]; + } +} diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/package-info.java b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/package-info.java new file mode 100644 index 00000000000..d146ba87dc9 --- /dev/null +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/filemove/package-info.java @@ -0,0 +1,24 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +@ParametersAreNonnullByDefault +package org.sonar.server.computation.filemove; + +import javax.annotation.ParametersAreNonnullByDefault; + diff --git a/server/sonar-server/src/main/java/org/sonar/server/computation/step/ReportComputationSteps.java b/server/sonar-server/src/main/java/org/sonar/server/computation/step/ReportComputationSteps.java index 80530f2c540..fc066ff22f3 100644 --- a/server/sonar-server/src/main/java/org/sonar/server/computation/step/ReportComputationSteps.java +++ b/server/sonar-server/src/main/java/org/sonar/server/computation/step/ReportComputationSteps.java @@ -26,6 +26,7 @@ import javax.annotation.Nonnull; import org.picocontainer.ComponentAdapter; import org.sonar.server.computation.container.ComputeEngineContainer; import org.sonar.server.computation.developer.PersistDevelopersDelegate; +import org.sonar.server.computation.filemove.FileMoveDetectionStep; import static com.google.common.collect.FluentIterable.from; @@ -48,6 +49,7 @@ public class ReportComputationSteps extends AbstractComputationSteps { // load project related stuffs LoadQualityGateStep.class, LoadPeriodsStep.class, + FileMoveDetectionStep.class, // load duplications related stuff LoadDuplicationsFromReportStep.class, diff --git a/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/FileMoveDetectionStepTest.java b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/FileMoveDetectionStepTest.java new file mode 100644 index 00000000000..a2dd17509b9 --- /dev/null +++ b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/FileMoveDetectionStepTest.java @@ -0,0 +1,483 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.Arrays; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import org.junit.Before; +import org.junit.Rule; +import org.junit.Test; +import org.mockito.ArgumentCaptor; +import org.sonar.core.hash.SourceHashComputer; +import org.sonar.core.hash.SourceLinesHashesComputer; +import org.sonar.db.DbClient; +import org.sonar.db.DbSession; +import org.sonar.db.component.ComponentDao; +import org.sonar.db.component.ComponentDtoWithSnapshotId; +import org.sonar.db.component.ComponentTreeQuery; +import org.sonar.db.source.FileSourceDao; +import org.sonar.db.source.FileSourceDto; +import org.sonar.server.computation.analysis.AnalysisMetadataHolderRule; +import org.sonar.server.computation.batch.TreeRootHolderRule; +import org.sonar.server.computation.component.Component; +import org.sonar.server.computation.snapshot.Snapshot; +import org.sonar.server.computation.source.SourceLinesRepositoryRule; + +import static com.google.common.base.Joiner.on; +import static java.util.Arrays.stream; +import static java.util.stream.Collectors.toList; +import static org.assertj.core.api.Java6Assertions.assertThat; +import static org.mockito.Matchers.any; +import static org.mockito.Matchers.eq; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.when; +import static org.sonar.api.resources.Qualifiers.FILE; +import static org.sonar.api.resources.Qualifiers.UNIT_TEST_FILE; +import static org.sonar.server.computation.component.ReportComponent.builder; + +public class FileMoveDetectionStepTest { + private static final long SNAPSHOT_ID = 98765; + private static final Snapshot SNAPSHOT = new Snapshot.Builder() + .setId(SNAPSHOT_ID) + .setCreatedAt(86521) + .build(); + private static final int ROOT_REF = 1; + private static final int FILE_1_REF = 2; + private static final int FILE_2_REF = 3; + private static final int FILE_3_REF = 4; + private static final Component FILE_1 = fileComponent(FILE_1_REF); + private static final Component FILE_2 = fileComponent(FILE_2_REF); + private static final Component FILE_3 = fileComponent(FILE_3_REF); + private static final String[] CONTENT1 = { + "package org.sonar.server.computation.filemove;", + "", + "public class Foo {", + " public String bar() {", + " return \"Doh!\";", + " }", + "}" + }; + private static final String[] LESS_CONTENT1 = { + "package org.sonar.server.computation.filemove;", + "", + "public class Foo {", + "}" + }; + public static final String[] CONTENT_EMPTY = { + "" + }; + private static final String[] CONTENT2 = { + "package org.sonar.ce.queue;", + "", + "import com.google.common.base.MoreObjects;", + "import javax.annotation.CheckForNull;", + "import javax.annotation.Nullable;", + "import javax.annotation.concurrent.Immutable;", + "", + "import static com.google.common.base.Strings.emptyToNull;", + "import static java.util.Objects.requireNonNull;", + "", + "@Immutable", + "public class CeTask {", + "", + ", private final String type;", + ", private final String uuid;", + ", private final String componentUuid;", + ", private final String componentKey;", + ", private final String componentName;", + ", private final String submitterLogin;", + "", + ", private CeTask(Builder builder) {", + ", this.uuid = requireNonNull(emptyToNull(builder.uuid));", + ", this.type = requireNonNull(emptyToNull(builder.type));", + ", this.componentUuid = emptyToNull(builder.componentUuid);", + ", this.componentKey = emptyToNull(builder.componentKey);", + ", this.componentName = emptyToNull(builder.componentName);", + ", this.submitterLogin = emptyToNull(builder.submitterLogin);", + ", }", + "", + ", public String getUuid() {", + ", return uuid;", + ", }", + "", + ", public String getType() {", + ", return type;", + ", }", + "", + ", @CheckForNull", + ", public String getComponentUuid() {", + ", return componentUuid;", + ", }", + "", + ", @CheckForNull", + ", public String getComponentKey() {", + ", return componentKey;", + ", }", + "", + ", @CheckForNull", + ", public String getComponentName() {", + ", return componentName;", + ", }", + "", + ", @CheckForNull", + ", public String getSubmitterLogin() {", + ", return submitterLogin;", + ", }", + ",}", + }; + // removed immutable annotation + private static final String[] LESS_CONTENT2 = { + "package org.sonar.ce.queue;", + "", + "import com.google.common.base.MoreObjects;", + "import javax.annotation.CheckForNull;", + "import javax.annotation.Nullable;", + "", + "import static com.google.common.base.Strings.emptyToNull;", + "import static java.util.Objects.requireNonNull;", + "", + "public class CeTask {", + "", + ", private final String type;", + ", private final String uuid;", + ", private final String componentUuid;", + ", private final String componentKey;", + ", private final String componentName;", + ", private final String submitterLogin;", + "", + ", private CeTask(Builder builder) {", + ", this.uuid = requireNonNull(emptyToNull(builder.uuid));", + ", this.type = requireNonNull(emptyToNull(builder.type));", + ", this.componentUuid = emptyToNull(builder.componentUuid);", + ", this.componentKey = emptyToNull(builder.componentKey);", + ", this.componentName = emptyToNull(builder.componentName);", + ", this.submitterLogin = emptyToNull(builder.submitterLogin);", + ", }", + "", + ", public String getUuid() {", + ", return uuid;", + ", }", + "", + ", public String getType() {", + ", return type;", + ", }", + "", + ", @CheckForNull", + ", public String getComponentUuid() {", + ", return componentUuid;", + ", }", + "", + ", @CheckForNull", + ", public String getComponentKey() {", + ", return componentKey;", + ", }", + "", + ", @CheckForNull", + ", public String getComponentName() {", + ", return componentName;", + ", }", + "", + ", @CheckForNull", + ", public String getSubmitterLogin() {", + ", return submitterLogin;", + ", }", + ",}", + }; + + @Rule + public AnalysisMetadataHolderRule analysisMetadataHolder = new AnalysisMetadataHolderRule(); + @Rule + public TreeRootHolderRule treeRootHolder = new TreeRootHolderRule(); + @Rule + public SourceLinesRepositoryRule sourceLinesRepository = new SourceLinesRepositoryRule(); + @Rule + public MutableMovedFilesRepositoryRule movedFilesRepository = new MutableMovedFilesRepositoryRule(); + + private DbClient dbClient = mock(DbClient.class); + private DbSession dbSession = mock(DbSession.class); + private ComponentDao componentDao = mock(ComponentDao.class); + private FileSourceDao fileSourceDao = mock(FileSourceDao.class); + private FileSimilarity fileSimilarity = new FileSimilarityImpl(new SourceSimilarityImpl()); + private long dbIdGenerator = 0; + + private FileMoveDetectionStep underTest = new FileMoveDetectionStep(analysisMetadataHolder, treeRootHolder, dbClient, + sourceLinesRepository, fileSimilarity, movedFilesRepository); + + @Before + public void setUp() throws Exception { + when(dbClient.openSession(false)).thenReturn(dbSession); + when(dbClient.componentDao()).thenReturn(componentDao); + when(dbClient.fileSourceDao()).thenReturn(fileSourceDao); + } + + @Test + public void getDescription_returns_description() { + assertThat(underTest.getDescription()).isEqualTo("Detect file moves"); + } + + @Test + public void execute_detects_no_move_if_baseProjectSnaphost_is_null() { + analysisMetadataHolder.setBaseProjectSnapshot(null); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_baseSnapshot_has_no_file_and_report_has_no_file() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_baseSnapshot_has_no_file() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + setFilesInReport(FILE_1, FILE_2); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_retrieves_only_file_and_unit_tests_from_last_snapshot() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + ArgumentCaptor captor = ArgumentCaptor.forClass(ComponentTreeQuery.class); + when(componentDao.selectAllChildren(eq(dbSession), captor.capture())) + .thenReturn(Collections.emptyList()); + + underTest.execute(); + + ComponentTreeQuery query = captor.getValue(); + assertThat(query.getBaseSnapshot().getId()).isEqualTo(SNAPSHOT_ID); + assertThat(query.getBaseSnapshot().getRootId()).isEqualTo(SNAPSHOT_ID); + assertThat(query.getPage()).isEqualTo(1); + assertThat(query.getPageSize()).isEqualTo(Integer.MAX_VALUE); + assertThat(query.getSqlSort()).isEqualTo("LOWER(p.name) ASC, p.name ASC"); + assertThat(query.getQualifiers()).containsOnly(FILE, UNIT_TEST_FILE); + } + + @Test + public void execute_detects_no_move_if_there_is_no_file_in_report() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(1); + setFilesInReport(); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_file_key_exists_in_both_DB_and_report() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(FILE_1.getKey(), FILE_2.getKey()); + setFilesInReport(FILE_2, FILE_1); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_move_if_content_of_file_is_same_in_DB_and_report() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + ComponentDtoWithSnapshotId[] dtos = mockComponentsForSnapshot(FILE_1.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT1); + setFilesInReport(FILE_2); + setFileContentInReport(FILE_2_REF, CONTENT1); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).containsExactly(FILE_2); + MovedFilesRepository.OriginalFile originalFile = movedFilesRepository.getOriginalFile(FILE_2).get(); + assertThat(originalFile.getId()).isEqualTo(dtos[0].getId()); + assertThat(originalFile.getKey()).isEqualTo(dtos[0].getKey()); + assertThat(originalFile.getUuid()).isEqualTo(dtos[0].uuid()); + } + + @Test + public void execute_detects_no_move_if_content_of_file_is_not_similar_enough() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(FILE_1.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT1); + setFilesInReport(FILE_2); + setFileContentInReport(FILE_2_REF, LESS_CONTENT1); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_content_of_file_is_empty_in_DB() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(FILE_1.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT_EMPTY); + setFilesInReport(FILE_2); + setFileContentInReport(FILE_2_REF, CONTENT1); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_content_of_file_is_empty_in_report() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(FILE_1.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT1); + setFilesInReport(FILE_2); + setFileContentInReport(FILE_2_REF, CONTENT_EMPTY); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_two_added_files_have_same_content_as_the_one_in_db() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(FILE_1.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT1); + setFilesInReport(FILE_2, FILE_3); + setFileContentInReport(FILE_2_REF, CONTENT1); + setFileContentInReport(FILE_3_REF, CONTENT1); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_no_move_if_two_deleted_files_have_same_content_as_the_one_added() { + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + mockComponentsForSnapshot(FILE_1.getKey(), FILE_2.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT1); + mockContentOfFileIdDb(FILE_2.getKey(), CONTENT1); + setFilesInReport(FILE_3); + setFileContentInReport(FILE_3_REF, CONTENT1); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).isEmpty(); + } + + @Test + public void execute_detects_several_moves() { + // testing: + // - file1 renamed to file3 + // - file2 deleted + // - file4 untouched + // - file5 renamed to file6 with a small change + analysisMetadataHolder.setBaseProjectSnapshot(SNAPSHOT); + Component file4 = fileComponent(5); + Component file5 = fileComponent(6); + Component file6 = fileComponent(7); + ComponentDtoWithSnapshotId[] dtos = mockComponentsForSnapshot(FILE_1.getKey(), FILE_2.getKey(), file4.getKey(), file5.getKey()); + mockContentOfFileIdDb(FILE_1.getKey(), CONTENT1); + mockContentOfFileIdDb(FILE_2.getKey(), LESS_CONTENT1); + mockContentOfFileIdDb(file4.getKey(), new String[]{"e","f","g","h","i"}); + mockContentOfFileIdDb(file5.getKey(), CONTENT2); + setFilesInReport(FILE_3, file4, file6); + setFileContentInReport(FILE_3_REF, CONTENT1); + setFileContentInReport(file4.getReportAttributes().getRef(), new String[]{"a","b"}); + setFileContentInReport(file6.getReportAttributes().getRef(), LESS_CONTENT2); + + underTest.execute(); + + assertThat(movedFilesRepository.getComponentsWithOriginal()).containsOnly(FILE_3, file6); + MovedFilesRepository.OriginalFile originalFile2 = movedFilesRepository.getOriginalFile(FILE_3).get(); + assertThat(originalFile2.getId()).isEqualTo(dtos[0].getId()); + assertThat(originalFile2.getKey()).isEqualTo(dtos[0].getKey()); + assertThat(originalFile2.getUuid()).isEqualTo(dtos[0].uuid()); + MovedFilesRepository.OriginalFile originalFile5 = movedFilesRepository.getOriginalFile(file6).get(); + assertThat(originalFile5.getId()).isEqualTo(dtos[3].getId()); + assertThat(originalFile5.getKey()).isEqualTo(dtos[3].getKey()); + assertThat(originalFile5.getUuid()).isEqualTo(dtos[3].uuid()); + } + + private void setFileContentInReport(int ref, String[] content) { + sourceLinesRepository.addLines(ref, content); + } + + private void mockContentOfFileIdDb(String key, String[] content) { + SourceLinesHashesComputer linesHashesComputer = new SourceLinesHashesComputer(); + SourceHashComputer sourceHashComputer = new SourceHashComputer(); + Iterator lineIterator = Arrays.asList(content).iterator(); + while (lineIterator.hasNext()) { + String line = lineIterator.next(); + linesHashesComputer.addLine(line); + sourceHashComputer.addLine(line, lineIterator.hasNext()); + } + + when(fileSourceDao.selectSourceByFileUuid(dbSession, componentUuidOf(key))) + .thenReturn(new FileSourceDto() + .setLineHashes(on('\n').join(linesHashesComputer.getLineHashes())) + .setSrcHash(sourceHashComputer.getHash())); + } + + private void setFilesInReport(Component... files) { + treeRootHolder.setRoot(builder(Component.Type.PROJECT, ROOT_REF) + .addChildren(files) + .build()); + } + + private ComponentDtoWithSnapshotId[] mockComponentsForSnapshot(String... componentKeys) { + return mockComponentsForSnapshot(SNAPSHOT_ID, componentKeys); + } + + private ComponentDtoWithSnapshotId[] mockComponentsForSnapshot(long snapshotId, String... componentKeys) { + List componentDtoWithSnapshotIds = stream(componentKeys) + .map(key -> newComponentDto(snapshotId, key)) + .collect(toList()); + when(componentDao.selectAllChildren(eq(dbSession), any(ComponentTreeQuery.class))) + .thenReturn(componentDtoWithSnapshotIds); + return componentDtoWithSnapshotIds.toArray(new ComponentDtoWithSnapshotId[componentDtoWithSnapshotIds.size()]); + } + + private ComponentDtoWithSnapshotId newComponentDto(long snapshotId, String key) { + ComponentDtoWithSnapshotId res = new ComponentDtoWithSnapshotId(); + res.setSnapshotId(snapshotId) + .setId(dbIdGenerator) + .setKey(key) + .setUuid(componentUuidOf(key)) + .setPath("path_" + key); + dbIdGenerator++; + return res; + } + + private static String componentUuidOf(String key) { + return "uuid_" + key; + } + + private static Component fileComponent(int ref) { + return builder(Component.Type.FILE, ref) + .setPath("report_path" + ref) + .build(); + } + +} diff --git a/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImplTest.java b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImplTest.java new file mode 100644 index 00000000000..15bbc7b75a6 --- /dev/null +++ b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryImplTest.java @@ -0,0 +1,140 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.Random; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; +import org.sonar.server.computation.component.Component; +import org.sonar.server.computation.component.ViewsComponent; + +import static org.assertj.core.api.Assertions.assertThat; +import static org.assertj.core.api.Assertions.fail; +import static org.assertj.guava.api.Assertions.assertThat; +import static org.sonar.server.computation.component.ReportComponent.builder; + +public class MutableMovedFilesRepositoryImplTest { + private static final Component SOME_FILE = builder(Component.Type.FILE, 1).build(); + private static final Component[] COMPONENTS_BUT_FILE = { + builder(Component.Type.PROJECT, 1).build(), + builder(Component.Type.MODULE, 1).build(), + builder(Component.Type.DIRECTORY, 1).build(), + ViewsComponent.builder(Component.Type.VIEW, 1).build(), + ViewsComponent.builder(Component.Type.SUBVIEW, 1).build(), + ViewsComponent.builder(Component.Type.PROJECT_VIEW, 1).build() + }; + private static final MovedFilesRepository.OriginalFile SOME_ORIGINAL_FILE = new MovedFilesRepository.OriginalFile(100, "uuid for 100", "key for 100"); + + @Rule + public ExpectedException expectedException = ExpectedException.none(); + + private MutableMovedFilesRepositoryImpl underTest = new MutableMovedFilesRepositoryImpl(); + + @Test + public void setOriginalFile_throws_NPE_when_file_is_null() { + expectedException.expect(NullPointerException.class); + expectedException.expectMessage("file can't be null"); + + underTest.setOriginalFile(null, SOME_ORIGINAL_FILE); + } + + @Test + public void setOriginalFile_throws_NPE_when_originalFile_is_null() { + expectedException.expect(NullPointerException.class); + expectedException.expectMessage("originalFile can't be null"); + + underTest.setOriginalFile(SOME_FILE, null); + } + + @Test + public void setOriginalFile_throws_IAE_when_type_is_no_FILE() { + for (Component component : COMPONENTS_BUT_FILE) { + try { + underTest.setOriginalFile(component, SOME_ORIGINAL_FILE); + fail("should have raised a NPE"); + } catch (IllegalArgumentException e) { + assertThat(e) + .isInstanceOf(IllegalArgumentException.class) + .hasMessage("file must be of type FILE"); + } + } + } + + @Test + public void setOriginalFile_throws_ISE_if_settings_another_originalFile() { + underTest.setOriginalFile(SOME_FILE, SOME_ORIGINAL_FILE); + + expectedException.expect(IllegalStateException.class); + expectedException.expectMessage("Original file OriginalFile{id=100, uuid='uuid for 100', key='key for 100'} " + + "already registered for file ReportComponent{ref=1, key='key_1', type=FILE}"); + + underTest.setOriginalFile(SOME_FILE, new MovedFilesRepository.OriginalFile(987, "uudi", "key")); + } + + @Test + public void setOriginalFile_does_not_fail_if_same_original_file_is_added_multiple_times_for_the_same_component() { + underTest.setOriginalFile(SOME_FILE, SOME_ORIGINAL_FILE); + + for (int i = 0; i < 1 + Math.abs(new Random().nextInt(10)); i++) { + underTest.setOriginalFile(SOME_FILE, SOME_ORIGINAL_FILE); + } + } + + @Test + public void setOriginalFile_does_not_fail_when_originalFile_is_added_twice_for_different_files() { + underTest.setOriginalFile(SOME_FILE, SOME_ORIGINAL_FILE); + underTest.setOriginalFile(builder(Component.Type.FILE, 2).build(), SOME_ORIGINAL_FILE); + } + + @Test + public void getOriginalFile_throws_NPE_when_file_is_null() { + expectedException.expect(NullPointerException.class); + expectedException.expectMessage("file can't be null"); + + underTest.getOriginalFile(null); + } + + @Test + public void getOriginalFile_returns_absent_for_any_component_type_when_empty() { + assertThat(underTest.getOriginalFile(SOME_FILE)).isAbsent(); + for (Component component : COMPONENTS_BUT_FILE) { + assertThat(underTest.getOriginalFile(component)).isAbsent(); + } + } + + @Test + public void getOriginalFile_returns_absent_for_any_type_of_Component_but_file_when_non_empty() { + underTest.setOriginalFile(SOME_FILE, SOME_ORIGINAL_FILE); + + for (Component component : COMPONENTS_BUT_FILE) { + assertThat(underTest.getOriginalFile(component)).isAbsent(); + } + assertThat(underTest.getOriginalFile(SOME_FILE)).contains(SOME_ORIGINAL_FILE); + } + + @Test + public void getOriginalFile_returns_originalFile_base_on_file_key() { + underTest.setOriginalFile(SOME_FILE, SOME_ORIGINAL_FILE); + + assertThat(underTest.getOriginalFile(SOME_FILE)).contains(SOME_ORIGINAL_FILE); + assertThat(underTest.getOriginalFile(builder(Component.Type.FILE, 1).setUuid("toto").build())).contains(SOME_ORIGINAL_FILE); + } +} diff --git a/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryRule.java b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryRule.java new file mode 100644 index 00000000000..3bcb077f800 --- /dev/null +++ b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/MutableMovedFilesRepositoryRule.java @@ -0,0 +1,60 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import com.google.common.base.Optional; +import java.util.HashSet; +import java.util.Set; +import javax.annotation.CheckForNull; +import org.junit.rules.ExternalResource; +import org.sonar.server.computation.component.Component; + +public class MutableMovedFilesRepositoryRule extends ExternalResource implements MutableMovedFilesRepository { + @CheckForNull + private MutableMovedFilesRepository delegate; + private final Set componentsWithOriginal = new HashSet<>(); + + @Override + protected void before() throws Throwable { + this.delegate = new MutableMovedFilesRepositoryImpl(); + this.componentsWithOriginal.clear(); + } + + @Override + protected void after() { + this.delegate = null; + this.componentsWithOriginal.clear(); + } + + @Override + public void setOriginalFile(Component file, OriginalFile originalFile) { + this.delegate.setOriginalFile(file, originalFile); + this.componentsWithOriginal.add(file); + } + + @Override + public Optional getOriginalFile(Component file) { + return this.delegate.getOriginalFile(file); + } + + public Set getComponentsWithOriginal() { + return componentsWithOriginal; + } +} diff --git a/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/SourceSimilarityImplTest.java b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/SourceSimilarityImplTest.java new file mode 100644 index 00000000000..8789b875b47 --- /dev/null +++ b/server/sonar-server/src/test/java/org/sonar/server/computation/filemove/SourceSimilarityImplTest.java @@ -0,0 +1,56 @@ +/* + * SonarQube + * Copyright (C) 2009-2016 SonarSource SA + * mailto:contact AT sonarsource DOT com + * + * This program 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. + * + * This program 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 this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +package org.sonar.server.computation.filemove; + +import java.util.List; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; + +import static java.util.Arrays.asList; +import static org.assertj.core.api.Assertions.assertThat; + +public class SourceSimilarityImplTest { + + @Rule + public ExpectedException expectedException = ExpectedException.none(); + + SourceSimilarityImpl underTest = new SourceSimilarityImpl(); + + @Test + public void zero_if_fully_different() { + List left = asList("a", "b", "c"); + List right = asList("d", "e"); + assertThat(underTest.score(left, right)).isEqualTo(0); + } + + @Test + public void one_hundred_if_same() { + assertThat(underTest.score(asList("a", "b", "c"), asList("a", "b", "c"))).isEqualTo(100); + assertThat(underTest.score(asList(""), asList(""))).isEqualTo(100); + } + + @Test + public void partially_same() { + assertThat(underTest.score(asList("a", "b", "c", "d"), asList("a", "b", "e", "f"))).isEqualTo(50); + assertThat(underTest.score(asList("a"), asList("a", "b", "c"))).isEqualTo(33); + assertThat(underTest.score(asList("a", "b", "c"), asList("a"))).isEqualTo(33); + } +} -- 2.39.5