diff options
| -rw-r--r-- | clang/include/clang/Analysis/CloneDetection.h | 33 | ||||
| -rw-r--r-- | clang/lib/Analysis/CloneDetection.cpp | 28 | ||||
| -rw-r--r-- | clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp | 10 | ||||
| -rw-r--r-- | clang/unittests/Analysis/CloneDetectionTest.cpp | 6 |
4 files changed, 49 insertions, 28 deletions
diff --git a/clang/include/clang/Analysis/CloneDetection.h b/clang/include/clang/Analysis/CloneDetection.h index e696443037d..eba4ea57618 100644 --- a/clang/include/clang/Analysis/CloneDetection.h +++ b/clang/include/clang/Analysis/CloneDetection.h @@ -252,22 +252,25 @@ public: std::function<bool(const StmtSequence &, const StmtSequence &)> Compare); }; -/// Searches all children of the given clones for type II clones (i.e. they are -/// identical in every aspect beside the used variable names). -class RecursiveCloneTypeIIConstraint { - - /// Generates and saves a hash code for the given Stmt. - /// \param S The given Stmt. - /// \param D The Decl containing S. - /// \param StmtsByHash Output parameter that will contain the hash codes for - /// each StmtSequence in the given Stmt. - /// \return The hash code of the given Stmt. - /// - /// If the given Stmt is a CompoundStmt, this method will also generate - /// hashes for all possible StmtSequences in the children of this Stmt. - size_t saveHash(const Stmt *S, const Decl *D, - std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash); +/// This constraint moves clones into clone groups of type II via hashing. +/// +/// Clones with different hash values are moved into separate clone groups. +/// Collisions are possible, and this constraint does nothing to address this +/// them. Add the slower RecursiveCloneTypeIIVerifyConstraint later in the +/// constraint chain, not necessarily immediately, to eliminate hash collisions +/// through a more detailed analysis. +class RecursiveCloneTypeIIHashConstraint { +public: + void constrain(std::vector<CloneDetector::CloneGroup> &Sequences); +}; +/// This constraint moves clones into clone groups of type II by comparing them. +/// +/// Clones that aren't type II clones are moved into separate clone groups. +/// In contrast to the RecursiveCloneTypeIIHashConstraint, all clones in a clone +/// group are guaranteed to be be type II clones of each other, but it is too +/// slow to efficiently handle large amounts of clones. +class RecursiveCloneTypeIIVerifyConstraint { public: void constrain(std::vector<CloneDetector::CloneGroup> &Sequences); }; diff --git a/clang/lib/Analysis/CloneDetection.cpp b/clang/lib/Analysis/CloneDetection.cpp index 1cce6a4d7d1..637e0428baf 100644 --- a/clang/lib/Analysis/CloneDetection.cpp +++ b/clang/lib/Analysis/CloneDetection.cpp @@ -238,9 +238,18 @@ static size_t createHash(llvm::MD5 &Hash) { return HashCode; } -size_t RecursiveCloneTypeIIConstraint::saveHash( - const Stmt *S, const Decl *D, - std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) { +/// Generates and saves a hash code for the given Stmt. +/// \param S The given Stmt. +/// \param D The Decl containing S. +/// \param StmtsByHash Output parameter that will contain the hash codes for +/// each StmtSequence in the given Stmt. +/// \return The hash code of the given Stmt. +/// +/// If the given Stmt is a CompoundStmt, this method will also generate +/// hashes for all possible StmtSequences in the children of this Stmt. +static size_t +saveHash(const Stmt *S, const Decl *D, + std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) { llvm::MD5 Hash; ASTContext &Context = D->getASTContext(); @@ -340,7 +349,7 @@ static bool areSequencesClones(const StmtSequence &LHS, return DataLHS == DataRHS; } -void RecursiveCloneTypeIIConstraint::constrain( +void RecursiveCloneTypeIIHashConstraint::constrain( std::vector<CloneDetector::CloneGroup> &Sequences) { // FIXME: Maybe we can do this in-place and don't need this additional vector. std::vector<CloneDetector::CloneGroup> Result; @@ -381,8 +390,7 @@ void RecursiveCloneTypeIIConstraint::constrain( for (; i < StmtsByHash.size(); ++i) { // A different hash value means we have reached the end of the sequence. - if (PrototypeHash != StmtsByHash[i].first || - !areSequencesClones(StmtsByHash[i].second, Current.second)) { + if (PrototypeHash != StmtsByHash[i].first) { // The current sequence could be the start of a new CloneGroup. So we // decrement i so that we visit it again in the outer loop. // Note: i can never be 0 at this point because we are just comparing @@ -405,6 +413,14 @@ void RecursiveCloneTypeIIConstraint::constrain( Sequences = Result; } +void RecursiveCloneTypeIIVerifyConstraint::constrain( + std::vector<CloneDetector::CloneGroup> &Sequences) { + CloneConstraint::splitCloneGroups( + Sequences, [](const StmtSequence &A, const StmtSequence &B) { + return areSequencesClones(A, B); + }); +} + size_t MinComplexityConstraint::calculateStmtComplexity( const StmtSequence &Seq, const std::string &ParentMacroStack) { if (Seq.empty()) diff --git a/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp index 83955c586b6..efcb8662a66 100644 --- a/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp @@ -81,11 +81,11 @@ void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU, // because reportSuspiciousClones() wants to search them for errors. std::vector<CloneDetector::CloneGroup> AllCloneGroups; - Detector.findClones(AllCloneGroups, - FilenamePatternConstraint(IgnoredFilesPattern), - RecursiveCloneTypeIIConstraint(), - MinComplexityConstraint(MinComplexity), - MinGroupSizeConstraint(2), OnlyLargestCloneConstraint()); + Detector.findClones( + AllCloneGroups, FilenamePatternConstraint(IgnoredFilesPattern), + RecursiveCloneTypeIIHashConstraint(), MinGroupSizeConstraint(2), + MinComplexityConstraint(MinComplexity), + RecursiveCloneTypeIIVerifyConstraint(), OnlyLargestCloneConstraint()); if (ReportSuspiciousClones) reportSuspiciousClones(BR, Mgr, AllCloneGroups); diff --git a/clang/unittests/Analysis/CloneDetectionTest.cpp b/clang/unittests/Analysis/CloneDetectionTest.cpp index 6d8ce3495fa..965a4bc3083 100644 --- a/clang/unittests/Analysis/CloneDetectionTest.cpp +++ b/clang/unittests/Analysis/CloneDetectionTest.cpp @@ -69,8 +69,9 @@ TEST(CloneDetector, FilterFunctionsByName) { // all statements from functions which names start with "bar". std::vector<CloneDetector::CloneGroup> CloneGroups; Detector.findClones(CloneGroups, NoBarFunctionConstraint(), - RecursiveCloneTypeIIConstraint(), + RecursiveCloneTypeIIHashConstraint(), MinComplexityConstraint(2), MinGroupSizeConstraint(2), + RecursiveCloneTypeIIVerifyConstraint(), OnlyLargestCloneConstraint()); ASSERT_EQ(CloneGroups.size(), 1u); @@ -86,8 +87,9 @@ TEST(CloneDetector, FilterFunctionsByName) { // Retry above's example without the filter... CloneGroups.clear(); - Detector.findClones(CloneGroups, RecursiveCloneTypeIIConstraint(), + Detector.findClones(CloneGroups, RecursiveCloneTypeIIHashConstraint(), MinComplexityConstraint(2), MinGroupSizeConstraint(2), + RecursiveCloneTypeIIVerifyConstraint(), OnlyLargestCloneConstraint()); ASSERT_EQ(CloneGroups.size(), 1u); ASSERT_EQ(CloneGroups.front().size(), 4u); |
