From 727ea63e6e82677f6e10e05e08bc7d6bdbae3111 Mon Sep 17 00:00:00 2001 From: Artem Dergachev Date: Wed, 5 Apr 2017 15:06:17 +0000 Subject: [PATCH] Revert "[analyzer] Add a modular constraint system to the CloneDetector" This reverts commit r299544. Crashes on tests on some buildbots. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@299550 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Analysis/CloneDetection.h | 349 +++----- lib/Analysis/CloneDetection.cpp | 887 +++++++++++-------- lib/StaticAnalyzer/Checkers/CloneChecker.cpp | 100 +-- unittests/Analysis/CMakeLists.txt | 5 +- unittests/Analysis/CloneDetectionTest.cpp | 110 --- 5 files changed, 662 insertions(+), 789 deletions(-) delete mode 100644 unittests/Analysis/CloneDetectionTest.cpp diff --git a/include/clang/Analysis/CloneDetection.h b/include/clang/Analysis/CloneDetection.h index a433f709d2..51cad7a96d 100644 --- a/include/clang/Analysis/CloneDetection.h +++ b/include/clang/Analysis/CloneDetection.h @@ -16,7 +16,9 @@ #define LLVM_CLANG_AST_CLONEDETECTION_H #include "clang/Basic/SourceLocation.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/ADT/StringMap.h" + #include namespace clang { @@ -27,7 +29,7 @@ class VarDecl; class ASTContext; class CompoundStmt; -/// Identifies a list of statements. +/// \brief Identifies a list of statements. /// /// Can either identify a single arbitrary Stmt object, a continuous sequence of /// child statements inside a CompoundStmt or no statements at all. @@ -37,8 +39,8 @@ class StmtSequence { /// Stmt, then S is a pointer to this Stmt. const Stmt *S; - /// The declaration that contains the statements. - const Decl *D; + /// The related ASTContext for S. + ASTContext *Context; /// If EndIndex is non-zero, then S is a CompoundStmt and this StmtSequence /// instance is representing the CompoundStmt children inside the array @@ -47,7 +49,7 @@ class StmtSequence { unsigned EndIndex; public: - /// Constructs a StmtSequence holding multiple statements. + /// \brief Constructs a StmtSequence holding multiple statements. /// /// The resulting StmtSequence identifies a continuous sequence of statements /// in the body of the given CompoundStmt. Which statements of the body should @@ -55,20 +57,20 @@ public: /// that describe a non-empty sub-array in the body of the given CompoundStmt. /// /// \param Stmt A CompoundStmt that contains all statements in its body. - /// \param Decl The Decl containing this Stmt. + /// \param Context The ASTContext for the given CompoundStmt. /// \param StartIndex The inclusive start index in the children array of /// \p Stmt /// \param EndIndex The exclusive end index in the children array of \p Stmt. - StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex, - unsigned EndIndex); + StmtSequence(const CompoundStmt *Stmt, ASTContext &Context, + unsigned StartIndex, unsigned EndIndex); - /// Constructs a StmtSequence holding a single statement. + /// \brief Constructs a StmtSequence holding a single statement. /// /// \param Stmt An arbitrary Stmt. - /// \param Decl The Decl containing this Stmt. - StmtSequence(const Stmt *Stmt, const Decl *D); + /// \param Context The ASTContext for the given Stmt. + StmtSequence(const Stmt *Stmt, ASTContext &Context); - /// Constructs an empty StmtSequence. + /// \brief Constructs an empty StmtSequence. StmtSequence(); typedef const Stmt *const *iterator; @@ -108,12 +110,9 @@ public: bool empty() const { return size() == 0; } /// Returns the related ASTContext for the stored Stmts. - ASTContext &getASTContext() const; - - /// Returns the declaration that contains the stored Stmts. - const Decl *getContainingDecl() const { - assert(D); - return D; + ASTContext &getASTContext() const { + assert(Context); + return *Context; } /// Returns true if this objects holds a list of statements. @@ -151,214 +150,106 @@ public: bool contains(const StmtSequence &Other) const; }; -/// Searches for similar subtrees in the AST. +/// \brief Searches for clones in source code. /// -/// First, this class needs several declarations with statement bodies which -/// can be passed via analyzeCodeBody. Afterwards all statements can be -/// searched for clones by calling findClones with a given list of constraints -/// that should specify the wanted properties of the clones. -/// -/// The result of findClones can be further constrained with the constrainClones -/// method. +/// First, this class needs a translation unit which is passed via +/// \p analyzeTranslationUnit . It will then generate and store search data +/// for all statements inside the given translation unit. +/// Afterwards the generated data can be used to find code clones by calling +/// \p findClones . /// /// This class only searches for clones in exectuable source code /// (e.g. function bodies). Other clones (e.g. cloned comments or declarations) /// are not supported. class CloneDetector { - public: - /// A collection of StmtSequences that share an arbitrary property. - typedef llvm::SmallVector CloneGroup; + typedef unsigned DataPiece; + + /// Holds the data about a StmtSequence that is needed during the search for + /// code clones. + struct CloneSignature { + /// \brief The hash code of the StmtSequence. + /// + /// The initial clone groups that are formed during the search for clones + /// consist only of Sequences that share the same hash code. This makes this + /// value the central part of this heuristic that is needed to find clones + /// in a performant way. For this to work, the type of this variable + /// always needs to be small and fast to compare. + /// + /// Also, StmtSequences that are clones of each others have to share + /// the same hash code. StmtSequences that are not clones of each other + /// shouldn't share the same hash code, but if they do, it will only + /// degrade the performance of the hash search but doesn't influence + /// the correctness of the result. + size_t Hash; + + /// \brief The complexity of the StmtSequence. + /// + /// This value gives an approximation on how many direct or indirect child + /// statements are contained in the related StmtSequence. In general, the + /// greater this value, the greater the amount of statements. However, this + /// is only an approximation and the actual amount of statements can be + /// higher or lower than this value. Statements that are generated by the + /// compiler (e.g. macro expansions) for example barely influence the + /// complexity value. + /// + /// The main purpose of this value is to filter clones that are too small + /// and therefore probably not interesting enough for the user. + unsigned Complexity; + + /// \brief Creates an empty CloneSignature without any data. + CloneSignature() : Complexity(1) {} + + CloneSignature(llvm::hash_code Hash, unsigned Complexity) + : Hash(Hash), Complexity(Complexity) {} + }; - /// Generates and stores search data for all statements in the body of - /// the given Decl. - void analyzeCodeBody(const Decl *D); + /// Holds group of StmtSequences that are clones of each other and the + /// complexity value (see CloneSignature::Complexity) that all stored + /// StmtSequences have in common. + struct CloneGroup { + std::vector Sequences; + CloneSignature Signature; - /// Constrains the given list of clone groups with the given constraint. - /// - /// The constraint is expected to have a method with the signature - /// `void constrain(std::vector &Sequences)` - /// as this is the interface that the CloneDetector uses for applying the - /// constraint. The constraint is supposed to directly modify the passed list - /// so that all clones in the list fulfill the specific property this - /// constraint ensures. - template - static void constrainClones(std::vector &CloneGroups, T C) { - C.constrain(CloneGroups); - } + CloneGroup() {} - /// Constrains the given list of clone groups with the given list of - /// constraints. - /// - /// The constraints are applied in sequence in the order in which they are - /// passed to this function. - template - static void constrainClones(std::vector &CloneGroups, T1 C, - Ts... ConstraintList) { - constrainClones(CloneGroups, C); - constrainClones(CloneGroups, ConstraintList...); - } - - /// Searches for clones in all previously passed statements. - /// \param Result Output parameter to which all created clone groups are - /// added. - /// \param Passes The constraints that should be applied to the result. - template - void findClones(std::vector &Result, Ts... ConstraintList) { - // The initial assumption is that there is only one clone group and every - // statement is a clone of the others. This clone group will then be - // split up with the help of the constraints. - CloneGroup AllClones; - AllClones.reserve(Sequences.size()); - for (const auto &C : Sequences) { - AllClones.push_back(C); + CloneGroup(const StmtSequence &Seq, CloneSignature Signature) + : Signature(Signature) { + Sequences.push_back(Seq); } - Result.push_back(AllClones); - - constrainClones(Result, ConstraintList...); - } - -private: - CloneGroup Sequences; -}; - -/// This class is a utility class that contains utility functions for building -/// custom constraints. -class CloneConstraint { -public: - /// Removes all groups by using a filter function. - /// \param CloneGroups The list of CloneGroups that is supposed to be - /// filtered. - /// \param Filter The filter function that should return true for all groups - /// that should be removed from the list. - static void - filterGroups(std::vector &CloneGroups, - std::function Filter) { - CloneGroups.erase( - std::remove_if(CloneGroups.begin(), CloneGroups.end(), Filter), - CloneGroups.end()); - } - - /// Splits the given CloneGroups until the given Compare function returns true - /// for all clones in a single group. - /// \param CloneGroups A list of CloneGroups that should be modified. - /// \param Compare The comparison function that all clones are supposed to - /// pass. Should return true if and only if two clones belong - /// to the same CloneGroup. - static void splitCloneGroups( - std::vector &CloneGroups, - std::function 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> &StmtsByHash); - -public: - void constrain(std::vector &Sequences); -}; - -/// Ensures that every clone has at least the given complexity. -/// -/// Complexity is here defined as the total amount of children of a statement. -/// This constraint assumes the first statement in the group is representative -/// for all other statements in the group in terms of complexity. -class MinComplexityConstraint { - unsigned MinComplexity; - -public: - MinComplexityConstraint(unsigned MinComplexity) - : MinComplexity(MinComplexity) {} - - size_t calculateStmtComplexity(const StmtSequence &Seq, - const std::string &ParentMacroStack = ""); - - void constrain(std::vector &CloneGroups) { - CloneConstraint::filterGroups( - CloneGroups, [this](const CloneDetector::CloneGroup &A) { - if (!A.empty()) - return calculateStmtComplexity(A.front()) < MinComplexity; - else - return false; - }); - } -}; - -/// Ensures that all clone groups contain at least the given amount of clones. -class MinGroupSizeConstraint { - unsigned MinGroupSize; - -public: - MinGroupSizeConstraint(unsigned MinGroupSize = 2) - : MinGroupSize(MinGroupSize) {} - - void constrain(std::vector &CloneGroups) { - CloneConstraint::filterGroups(CloneGroups, - [this](const CloneDetector::CloneGroup &A) { - return A.size() < MinGroupSize; - }); - } -}; - -/// Ensures that no clone group fully contains another clone group. -struct OnlyLargestCloneConstraint { - void constrain(std::vector &Result); -}; - -/// Analyzes the pattern of the referenced variables in a statement. -class VariablePattern { - - /// Describes an occurence of a variable reference in a statement. - struct VariableOccurence { - /// The index of the associated VarDecl in the Variables vector. - size_t KindID; - /// The statement in the code where the variable was referenced. - const Stmt *Mention; - - VariableOccurence(size_t KindID, const Stmt *Mention) - : KindID(KindID), Mention(Mention) {} + /// \brief Returns false if and only if this group should be skipped when + /// searching for clones. + bool isValid() const { + // A clone group with only one member makes no sense, so we skip them. + return Sequences.size() > 1; + } }; - /// All occurences of referenced variables in the order of appearance. - std::vector Occurences; - /// List of referenced variables in the order of appearance. - /// Every item in this list is unique. - std::vector Variables; - - /// Adds a new variable referenced to this pattern. - /// \param VarDecl The declaration of the variable that is referenced. - /// \param Mention The SourceRange where this variable is referenced. - void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention); + /// \brief Generates and stores search data for all statements in the body of + /// the given Decl. + void analyzeCodeBody(const Decl *D); - /// Adds each referenced variable from the given statement. - void addVariables(const Stmt *S); + /// \brief Stores the CloneSignature to allow future querying. + void add(const StmtSequence &S, const CloneSignature &Signature); -public: - /// Creates an VariablePattern object with information about the given - /// StmtSequence. - VariablePattern(const StmtSequence &Sequence) { - for (const Stmt *S : Sequence) - addVariables(S); - } - - /// Describes two clones that reference their variables in a different pattern - /// which could indicate a programming error. + /// \brief Searches the provided statements for clones. + /// + /// \param Result Output parameter that is filled with a list of found + /// clone groups. Each group contains multiple StmtSequences + /// that were identified to be clones of each other. + /// \param MinGroupComplexity Only return clones which have at least this + /// complexity value. + /// \param CheckPatterns Returns only clone groups in which the referenced + /// variables follow the same pattern. + void findClones(std::vector &Result, unsigned MinGroupComplexity, + bool CheckPatterns = true); + + /// \brief Describes two clones that reference their variables in a different + /// pattern which could indicate a programming error. struct SuspiciousClonePair { - /// Utility class holding the relevant information about a single - /// clone in this pair. + /// \brief Utility class holding the relevant information about a single + /// clone in this pair. struct SuspiciousCloneInfo { /// The variable which referencing in this clone was against the pattern. const VarDecl *Variable; @@ -379,37 +270,17 @@ public: SuspiciousCloneInfo SecondCloneInfo; }; - /// Counts the differences between this pattern and the given one. - /// \param Other The given VariablePattern to compare with. - /// \param FirstMismatch Output parameter that will be filled with information - /// about the first difference between the two patterns. This parameter - /// can be a nullptr, in which case it will be ignored. - /// \return Returns the number of differences between the pattern this object - /// is following and the given VariablePattern. - /// - /// For example, the following statements all have the same pattern and this - /// function would return zero: - /// - /// if (a < b) return a; return b; - /// if (x < y) return x; return y; - /// if (u2 < u1) return u2; return u1; - /// - /// But the following statement has a different pattern (note the changed - /// variables in the return statements) and would have two differences when - /// compared with one of the statements above. - /// - /// if (a < b) return b; return a; - /// - /// This function should only be called if the related statements of the given - /// pattern and the statements of this objects are clones of each other. - unsigned countPatternDifferences( - const VariablePattern &Other, - VariablePattern::SuspiciousClonePair *FirstMismatch = nullptr); -}; + /// \brief Searches the provided statements for pairs of clones that don't + /// follow the same pattern when referencing variables. + /// \param Result Output parameter that will contain the clone pairs. + /// \param MinGroupComplexity Only clone pairs in which the clones have at + /// least this complexity value. + void findSuspiciousClones(std::vector &Result, + unsigned MinGroupComplexity); -/// Ensures that all clones reference variables in the same pattern. -struct MatchingVariablePatternConstraint { - void constrain(std::vector &CloneGroups); +private: + /// Stores all encountered StmtSequences alongside their CloneSignature. + std::vector> Sequences; }; } // end namespace clang diff --git a/lib/Analysis/CloneDetection.cpp b/lib/Analysis/CloneDetection.cpp index 11f3961050..e761738214 100644 --- a/lib/Analysis/CloneDetection.cpp +++ b/lib/Analysis/CloneDetection.cpp @@ -24,27 +24,27 @@ using namespace clang; -StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D, +StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context, unsigned StartIndex, unsigned EndIndex) - : S(Stmt), D(D), StartIndex(StartIndex), EndIndex(EndIndex) { + : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) { assert(Stmt && "Stmt must not be a nullptr"); assert(StartIndex < EndIndex && "Given array should not be empty"); assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt"); } -StmtSequence::StmtSequence(const Stmt *Stmt, const Decl *D) - : S(Stmt), D(D), StartIndex(0), EndIndex(0) {} +StmtSequence::StmtSequence(const Stmt *Stmt, ASTContext &Context) + : S(Stmt), Context(&Context), StartIndex(0), EndIndex(0) {} StmtSequence::StmtSequence() - : S(nullptr), D(nullptr), StartIndex(0), EndIndex(0) {} + : S(nullptr), Context(nullptr), StartIndex(0), EndIndex(0) {} bool StmtSequence::contains(const StmtSequence &Other) const { - // If both sequences reside in different declarations, they can never contain - // each other. - if (D != Other.D) + // If both sequences reside in different translation units, they can never + // contain each other. + if (Context != Other.Context) return false; - const SourceManager &SM = getASTContext().getSourceManager(); + const SourceManager &SM = Context->getSourceManager(); // Otherwise check if the start and end locations of the current sequence // surround the other sequence. @@ -76,11 +76,6 @@ StmtSequence::iterator StmtSequence::end() const { return CS->body_begin() + EndIndex; } -ASTContext &StmtSequence::getASTContext() const { - assert(D); - return D->getASTContext(); -} - SourceLocation StmtSequence::getStartLoc() const { return front()->getLocStart(); } @@ -91,8 +86,168 @@ SourceRange StmtSequence::getSourceRange() const { return SourceRange(getStartLoc(), getEndLoc()); } -/// Prints the macro name that contains the given SourceLocation into the given -/// raw_string_ostream. +namespace { + +/// \brief Analyzes the pattern of the referenced variables in a statement. +class VariablePattern { + + /// \brief Describes an occurence of a variable reference in a statement. + struct VariableOccurence { + /// The index of the associated VarDecl in the Variables vector. + size_t KindID; + /// The statement in the code where the variable was referenced. + const Stmt *Mention; + + VariableOccurence(size_t KindID, const Stmt *Mention) + : KindID(KindID), Mention(Mention) {} + }; + + /// All occurences of referenced variables in the order of appearance. + std::vector Occurences; + /// List of referenced variables in the order of appearance. + /// Every item in this list is unique. + std::vector Variables; + + /// \brief Adds a new variable referenced to this pattern. + /// \param VarDecl The declaration of the variable that is referenced. + /// \param Mention The SourceRange where this variable is referenced. + void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention) { + // First check if we already reference this variable + for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex) { + if (Variables[KindIndex] == VarDecl) { + // If yes, add a new occurence that points to the existing entry in + // the Variables vector. + Occurences.emplace_back(KindIndex, Mention); + return; + } + } + // If this variable wasn't already referenced, add it to the list of + // referenced variables and add a occurence that points to this new entry. + Occurences.emplace_back(Variables.size(), Mention); + Variables.push_back(VarDecl); + } + + /// \brief Adds each referenced variable from the given statement. + void addVariables(const Stmt *S) { + // Sometimes we get a nullptr (such as from IfStmts which often have nullptr + // children). We skip such statements as they don't reference any + // variables. + if (!S) + return; + + // Check if S is a reference to a variable. If yes, add it to the pattern. + if (auto D = dyn_cast(S)) { + if (auto VD = dyn_cast(D->getDecl()->getCanonicalDecl())) + addVariableOccurence(VD, D); + } + + // Recursively check all children of the given statement. + for (const Stmt *Child : S->children()) { + addVariables(Child); + } + } + +public: + /// \brief Creates an VariablePattern object with information about the given + /// StmtSequence. + VariablePattern(const StmtSequence &Sequence) { + for (const Stmt *S : Sequence) + addVariables(S); + } + + /// \brief Counts the differences between this pattern and the given one. + /// \param Other The given VariablePattern to compare with. + /// \param FirstMismatch Output parameter that will be filled with information + /// about the first difference between the two patterns. This parameter + /// can be a nullptr, in which case it will be ignored. + /// \return Returns the number of differences between the pattern this object + /// is following and the given VariablePattern. + /// + /// For example, the following statements all have the same pattern and this + /// function would return zero: + /// + /// if (a < b) return a; return b; + /// if (x < y) return x; return y; + /// if (u2 < u1) return u2; return u1; + /// + /// But the following statement has a different pattern (note the changed + /// variables in the return statements) and would have two differences when + /// compared with one of the statements above. + /// + /// if (a < b) return b; return a; + /// + /// This function should only be called if the related statements of the given + /// pattern and the statements of this objects are clones of each other. + unsigned countPatternDifferences( + const VariablePattern &Other, + CloneDetector::SuspiciousClonePair *FirstMismatch = nullptr) { + unsigned NumberOfDifferences = 0; + + assert(Other.Occurences.size() == Occurences.size()); + for (unsigned i = 0; i < Occurences.size(); ++i) { + auto ThisOccurence = Occurences[i]; + auto OtherOccurence = Other.Occurences[i]; + if (ThisOccurence.KindID == OtherOccurence.KindID) + continue; + + ++NumberOfDifferences; + + // If FirstMismatch is not a nullptr, we need to store information about + // the first difference between the two patterns. + if (FirstMismatch == nullptr) + continue; + + // Only proceed if we just found the first difference as we only store + // information about the first difference. + if (NumberOfDifferences != 1) + continue; + + const VarDecl *FirstSuggestion = nullptr; + // If there is a variable available in the list of referenced variables + // which wouldn't break the pattern if it is used in place of the + // current variable, we provide this variable as the suggested fix. + if (OtherOccurence.KindID < Variables.size()) + FirstSuggestion = Variables[OtherOccurence.KindID]; + + // Store information about the first clone. + FirstMismatch->FirstCloneInfo = + CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo( + Variables[ThisOccurence.KindID], ThisOccurence.Mention, + FirstSuggestion); + + // Same as above but with the other clone. We do this for both clones as + // we don't know which clone is the one containing the unintended + // pattern error. + const VarDecl *SecondSuggestion = nullptr; + if (ThisOccurence.KindID < Other.Variables.size()) + SecondSuggestion = Other.Variables[ThisOccurence.KindID]; + + // Store information about the second clone. + FirstMismatch->SecondCloneInfo = + CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo( + Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention, + SecondSuggestion); + + // SuspiciousClonePair guarantees that the first clone always has a + // suggested variable associated with it. As we know that one of the two + // clones in the pair always has suggestion, we swap the two clones + // in case the first clone has no suggested variable which means that + // the second clone has a suggested variable and should be first. + if (!FirstMismatch->FirstCloneInfo.Suggestion) + std::swap(FirstMismatch->FirstCloneInfo, + FirstMismatch->SecondCloneInfo); + + // This ensures that we always have at least one suggestion in a pair. + assert(FirstMismatch->FirstCloneInfo.Suggestion); + } + + return NumberOfDifferences; + } +}; +} + +/// \brief Prints the macro name that contains the given SourceLocation into +/// the given raw_string_ostream. static void printMacroName(llvm::raw_string_ostream &MacroStack, ASTContext &Context, SourceLocation Loc) { MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(), @@ -103,8 +258,8 @@ static void printMacroName(llvm::raw_string_ostream &MacroStack, MacroStack << " "; } -/// Returns a string that represents all macro expansions that expanded into the -/// given SourceLocation. +/// \brief Returns a string that represents all macro expansions that +/// expanded into the given SourceLocation. /// /// If 'getMacroStack(A) == getMacroStack(B)' is true, then the SourceLocations /// A and B are expanded from the same macros in the same order. @@ -124,9 +279,7 @@ static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) { } namespace { -typedef unsigned DataPiece; - -/// Collects the data of a single Stmt. +/// \brief Collects the data of a single Stmt. /// /// This class defines what a code clone is: If it collects for two statements /// the same data, then those two statements are considered to be clones of each @@ -139,11 +292,11 @@ template class StmtDataCollector : public ConstStmtVisitor> { ASTContext &Context; - /// The data sink to which all data is forwarded. + /// \brief The data sink to which all data is forwarded. T &DataConsumer; public: - /// Collects data of the given Stmt. + /// \brief Collects data of the given Stmt. /// \param S The given statement. /// \param Context The ASTContext of S. /// \param DataConsumer The data sink to which all data is forwarded. @@ -154,7 +307,7 @@ public: // Below are utility methods for appending different data to the vector. - void addData(DataPiece Integer) { + void addData(CloneDetector::DataPiece Integer) { DataConsumer.update( StringRef(reinterpret_cast(&Integer), sizeof(Integer))); } @@ -272,7 +425,7 @@ public: }) DEF_ADD_DATA(DeclStmt, { auto numDecls = std::distance(S->decl_begin(), S->decl_end()); - addData(static_cast(numDecls)); + addData(static_cast(numDecls)); for (const Decl *D : S->decls()) { if (const VarDecl *VD = dyn_cast(D)) { addData(VD->getType()); @@ -301,131 +454,199 @@ public: }; } // end anonymous namespace -void CloneDetector::analyzeCodeBody(const Decl *D) { - assert(D); - assert(D->hasBody()); - - Sequences.push_back(StmtSequence(D->getBody(), D)); -} - -/// Returns true if and only if \p Stmt contains at least one other -/// sequence in the \p Group. -static bool containsAnyInGroup(StmtSequence &Seq, - CloneDetector::CloneGroup &Group) { - for (StmtSequence &GroupSeq : Group) { - if (Seq.contains(GroupSeq)) - return true; - } - return false; -} +namespace { +/// Generates CloneSignatures for a set of statements and stores the results in +/// a CloneDetector object. +class CloneSignatureGenerator { -/// Returns true if and only if all sequences in \p OtherGroup are -/// contained by a sequence in \p Group. -static bool containsGroup(CloneDetector::CloneGroup &Group, - CloneDetector::CloneGroup &OtherGroup) { - // We have less sequences in the current group than we have in the other, - // so we will never fulfill the requirement for returning true. This is only - // possible because we know that a sequence in Group can contain at most - // one sequence in OtherGroup. - if (Group.size() < OtherGroup.size()) - return false; + CloneDetector &CD; + ASTContext &Context; - for (StmtSequence &Stmt : Group) { - if (!containsAnyInGroup(Stmt, OtherGroup)) - return false; - } - return true; -} + /// \brief Generates CloneSignatures for all statements in the given statement + /// tree and stores them in the CloneDetector. + /// + /// \param S The root of the given statement tree. + /// \param ParentMacroStack A string representing the macros that generated + /// the parent statement or an empty string if no + /// macros generated the parent statement. + /// See getMacroStack() for generating such a string. + /// \return The CloneSignature of the root statement. + CloneDetector::CloneSignature + generateSignatures(const Stmt *S, const std::string &ParentMacroStack) { + // Create an empty signature that will be filled in this method. + CloneDetector::CloneSignature Signature; + + llvm::MD5 Hash; + + // Collect all relevant data from S and hash it. + StmtDataCollector(S, Context, Hash); + + // Look up what macros expanded into the current statement. + std::string StartMacroStack = getMacroStack(S->getLocStart(), Context); + std::string EndMacroStack = getMacroStack(S->getLocEnd(), Context); + + // First, check if ParentMacroStack is not empty which means we are currently + // dealing with a parent statement which was expanded from a macro. + // If this parent statement was expanded from the same macros as this + // statement, we reduce the initial complexity of this statement to zero. + // This causes that a group of statements that were generated by a single + // macro expansion will only increase the total complexity by one. + // Note: This is not the final complexity of this statement as we still + // add the complexity of the child statements to the complexity value. + if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack && + EndMacroStack == ParentMacroStack)) { + Signature.Complexity = 0; + } -void OnlyLargestCloneConstraint::constrain( - std::vector &Result) { - std::vector IndexesToRemove; + // Storage for the signatures of the direct child statements. This is only + // needed if the current statement is a CompoundStmt. + std::vector ChildSignatures; + const CompoundStmt *CS = dyn_cast(S); - // Compare every group in the result with the rest. If one groups contains - // another group, we only need to return the bigger group. - // Note: This doesn't scale well, so if possible avoid calling any heavy - // function from this loop to minimize the performance impact. - for (unsigned i = 0; i < Result.size(); ++i) { - for (unsigned j = 0; j < Result.size(); ++j) { - // Don't compare a group with itself. - if (i == j) + // The signature of a statement includes the signatures of its children. + // Therefore we create the signatures for every child and add them to the + // current signature. + for (const Stmt *Child : S->children()) { + // Some statements like 'if' can have nullptr children that we will skip. + if (!Child) continue; - if (containsGroup(Result[j], Result[i])) { - IndexesToRemove.push_back(i); - break; - } - } - } + // Recursive call to create the signature of the child statement. This + // will also create and store all clone groups in this child statement. + // We pass only the StartMacroStack along to keep things simple. + auto ChildSignature = generateSignatures(Child, StartMacroStack); - // Erasing a list of indexes from the vector should be done with decreasing - // indexes. As IndexesToRemove is constructed with increasing values, we just - // reverse iterate over it to get the desired order. - for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); ++I) { - Result.erase(Result.begin() + *I); - } -} + // Add the collected data to the signature of the current statement. + Signature.Complexity += ChildSignature.Complexity; + Hash.update(StringRef(reinterpret_cast(&ChildSignature.Hash), + sizeof(ChildSignature.Hash))); -static size_t createHash(llvm::MD5 &Hash) { - size_t HashCode; + // If the current statement is a CompoundStatement, we need to store the + // signature for the generation of the sub-sequences. + if (CS) + ChildSignatures.push_back(ChildSignature); + } - // Create the final hash code for the current Stmt. - llvm::MD5::MD5Result HashResult; - Hash.final(HashResult); + // If the current statement is a CompoundStmt, we also need to create the + // clone groups from the sub-sequences inside the children. + if (CS) + handleSubSequences(CS, ChildSignatures); - // Copy as much as possible of the generated hash code to the Stmt's hash - // code. - std::memcpy(&HashCode, &HashResult, - std::min(sizeof(HashCode), sizeof(HashResult))); + // Create the final hash code for the current signature. + llvm::MD5::MD5Result HashResult; + Hash.final(HashResult); - return HashCode; -} + // Copy as much of the generated hash code to the signature's hash code. + std::memcpy(&Signature.Hash, &HashResult, + std::min(sizeof(Signature.Hash), sizeof(HashResult))); -size_t RecursiveCloneTypeIIConstraint::saveHash( - const Stmt *S, const Decl *D, - std::vector> &StmtsByHash) { - llvm::MD5 Hash; - ASTContext &Context = D->getASTContext(); + // Save the signature for the current statement in the CloneDetector object. + CD.add(StmtSequence(S, Context), Signature); - StmtDataCollector(S, Context, Hash); + return Signature; + } - auto CS = dyn_cast(S); - SmallVector ChildHashes; + /// \brief Adds all possible sub-sequences in the child array of the given + /// CompoundStmt to the CloneDetector. + /// \param CS The given CompoundStmt. + /// \param ChildSignatures A list of calculated signatures for each child in + /// the given CompoundStmt. + void handleSubSequences( + const CompoundStmt *CS, + const std::vector &ChildSignatures) { - for (const Stmt *S : S->children()) { - if (S == nullptr) { - ChildHashes.push_back(0); - continue; - } - size_t ChildHash = saveHash(S, D, StmtsByHash); - Hash.update( - StringRef(reinterpret_cast(&ChildHash), sizeof(ChildHash))); - ChildHashes.push_back(ChildHash); - } + // FIXME: This function has quadratic runtime right now. Check if skipping + // this function for too long CompoundStmts is an option. - if (CS) { + // The length of the sub-sequence. We don't need to handle sequences with + // the length 1 as they are already handled in CollectData(). for (unsigned Length = 2; Length <= CS->size(); ++Length) { + // The start index in the body of the CompoundStmt. We increase the + // position until the end of the sub-sequence reaches the end of the + // CompoundStmt body. for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) { - llvm::MD5 Hash; + // Create an empty signature and add the signatures of all selected + // child statements to it. + CloneDetector::CloneSignature SubSignature; + llvm::MD5 SubHash; + for (unsigned i = Pos; i < Pos + Length; ++i) { - size_t ChildHash = ChildHashes[i]; - Hash.update(StringRef(reinterpret_cast(&ChildHash), + SubSignature.Complexity += ChildSignatures[i].Complexity; + size_t ChildHash = ChildSignatures[i].Hash; + + SubHash.update(StringRef(reinterpret_cast(&ChildHash), sizeof(ChildHash))); } - StmtsByHash.push_back(std::make_pair( - createHash(Hash), StmtSequence(CS, D, Pos, Pos + Length))); + + // Create the final hash code for the current signature. + llvm::MD5::MD5Result HashResult; + SubHash.final(HashResult); + + // Copy as much of the generated hash code to the signature's hash code. + std::memcpy(&SubSignature.Hash, &HashResult, + std::min(sizeof(SubSignature.Hash), sizeof(HashResult))); + + // Save the signature together with the information about what children + // sequence we selected. + CD.add(StmtSequence(CS, Context, Pos, Pos + Length), SubSignature); } } } - size_t HashCode = createHash(Hash); - StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D))); - return HashCode; +public: + explicit CloneSignatureGenerator(CloneDetector &CD, ASTContext &Context) + : CD(CD), Context(Context) {} + + /// \brief Generates signatures for all statements in the given function body. + void consumeCodeBody(const Stmt *S) { generateSignatures(S, ""); } +}; +} // end anonymous namespace + +void CloneDetector::analyzeCodeBody(const Decl *D) { + assert(D); + assert(D->hasBody()); + CloneSignatureGenerator Generator(*this, D->getASTContext()); + Generator.consumeCodeBody(D->getBody()); +} + +void CloneDetector::add(const StmtSequence &S, + const CloneSignature &Signature) { + Sequences.push_back(std::make_pair(Signature, S)); } namespace { -/// Wrapper around FoldingSetNodeID that it can be used as the template -/// argument of the StmtDataCollector. +/// \brief Returns true if and only if \p Stmt contains at least one other +/// sequence in the \p Group. +bool containsAnyInGroup(StmtSequence &Stmt, CloneDetector::CloneGroup &Group) { + for (StmtSequence &GroupStmt : Group.Sequences) { + if (Stmt.contains(GroupStmt)) + return true; + } + return false; +} + +/// \brief Returns true if and only if all sequences in \p OtherGroup are +/// contained by a sequence in \p Group. +bool containsGroup(CloneDetector::CloneGroup &Group, + CloneDetector::CloneGroup &OtherGroup) { + // We have less sequences in the current group than we have in the other, + // so we will never fulfill the requirement for returning true. This is only + // possible because we know that a sequence in Group can contain at most + // one sequence in OtherGroup. + if (Group.Sequences.size() < OtherGroup.Sequences.size()) + return false; + + for (StmtSequence &Stmt : Group.Sequences) { + if (!containsAnyInGroup(Stmt, OtherGroup)) + return false; + } + return true; +} +} // end anonymous namespace + +namespace { +/// \brief Wrapper around FoldingSetNodeID that it can be used as the template +/// argument of the StmtDataCollector. class FoldingSetNodeIDWrapper { llvm::FoldingSetNodeID &FS; @@ -437,8 +658,8 @@ public: }; } // end anonymous namespace -/// Writes the relevant data from all statements and child statements -/// in the given StmtSequence into the given FoldingSetNodeID. +/// \brief Writes the relevant data from all statements and child statements +/// in the given StmtSequence into the given FoldingSetNodeID. static void CollectStmtSequenceData(const StmtSequence &Sequence, FoldingSetNodeIDWrapper &OutputData) { for (const Stmt *S : Sequence) { @@ -449,13 +670,13 @@ static void CollectStmtSequenceData(const StmtSequence &Sequence, if (!Child) continue; - CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()), + CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()), OutputData); } } } -/// Returns true if both sequences are clones of each other. +/// \brief Returns true if both sequences are clones of each other. static bool areSequencesClones(const StmtSequence &LHS, const StmtSequence &RHS) { // We collect the data from all statements in the sequence as we did before @@ -472,272 +693,202 @@ static bool areSequencesClones(const StmtSequence &LHS, return DataLHS == DataRHS; } -void RecursiveCloneTypeIIConstraint::constrain( - std::vector &Sequences) { - // FIXME: Maybe we can do this in-place and don't need this additional vector. - std::vector Result; - - for (CloneDetector::CloneGroup &Group : Sequences) { - // We assume in the following code that the Group is non-empty, so we - // skip all empty groups. - if (Group.empty()) - continue; - - std::vector> StmtsByHash; - - // Generate hash codes for all children of S and save them in StmtsByHash. - for (const StmtSequence &S : Group) { - saveHash(S.front(), S.getContainingDecl(), StmtsByHash); - } +/// \brief Finds all actual clone groups in a single group of presumed clones. +/// \param Result Output parameter to which all found groups are added. +/// \param Group A group of presumed clones. The clones are allowed to have a +/// different variable pattern and may not be actual clones of each +/// other. +/// \param CheckVariablePattern If true, every clone in a group that was added +/// to the output follows the same variable pattern as the other +/// clones in its group. +static void createCloneGroups(std::vector &Result, + const CloneDetector::CloneGroup &Group, + bool CheckVariablePattern) { + // We remove the Sequences one by one, so a list is more appropriate. + std::list UnassignedSequences(Group.Sequences.begin(), + Group.Sequences.end()); + + // Search for clones as long as there could be clones in UnassignedSequences. + while (UnassignedSequences.size() > 1) { + + // Pick the first Sequence as a protoype for a new clone group. + StmtSequence Prototype = UnassignedSequences.front(); + UnassignedSequences.pop_front(); + + CloneDetector::CloneGroup FilteredGroup(Prototype, Group.Signature); + + // Analyze the variable pattern of the prototype. Every other StmtSequence + // needs to have the same pattern to get into the new clone group. + VariablePattern PrototypeFeatures(Prototype); + + // Search all remaining StmtSequences for an identical variable pattern + // and assign them to our new clone group. + auto I = UnassignedSequences.begin(), E = UnassignedSequences.end(); + while (I != E) { + // If the sequence doesn't fit to the prototype, we have encountered + // an unintended hash code collision and we skip it. + if (!areSequencesClones(Prototype, *I)) { + ++I; + continue; + } - // Sort hash_codes in StmtsByHash. - std::stable_sort(StmtsByHash.begin(), StmtsByHash.end(), - [this](std::pair LHS, - std::pair RHS) { - return LHS.first < RHS.first; - }); - - // Check for each StmtSequence if its successor has the same hash value. - // We don't check the last StmtSequence as it has no successor. - // Note: The 'size - 1 ' in the condition is safe because we check for an - // empty Group vector at the beginning of this function. - for (unsigned i = 0; i < StmtsByHash.size() - 1; ++i) { - const auto Current = StmtsByHash[i]; - - // It's likely that we just found an sequence of StmtSequences that - // represent a CloneGroup, so we create a new group and start checking and - // adding the StmtSequences in this sequence. - CloneDetector::CloneGroup NewGroup; - - size_t PrototypeHash = Current.first; - - 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)) { - // 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 - // the hash of the Current StmtSequence with itself in the 'if' above. - assert(i != 0); - --i; - break; - } - // Same hash value means we should add the StmtSequence to the current - // group. - NewGroup.push_back(StmtsByHash[i].second); + // If we weren't asked to check for a matching variable pattern in clone + // groups we can add the sequence now to the new clone group. + // If we were asked to check for matching variable pattern, we first have + // to check that there are no differences between the two patterns and + // only proceed if they match. + if (!CheckVariablePattern || + VariablePattern(*I).countPatternDifferences(PrototypeFeatures) == 0) { + FilteredGroup.Sequences.push_back(*I); + I = UnassignedSequences.erase(I); + continue; } - // We created a new clone group with matching hash codes and move it to - // the result vector. - Result.push_back(NewGroup); + // We didn't found a matching variable pattern, so we continue with the + // next sequence. + ++I; } - } - // Sequences is the output parameter, so we copy our result into it. - Sequences = Result; -} -size_t MinComplexityConstraint::calculateStmtComplexity( - const StmtSequence &Seq, const std::string &ParentMacroStack) { - if (Seq.empty()) - return 0; - - size_t Complexity = 1; - - ASTContext &Context = Seq.getASTContext(); - - // Look up what macros expanded into the current statement. - std::string StartMacroStack = getMacroStack(Seq.getStartLoc(), Context); - std::string EndMacroStack = getMacroStack(Seq.getEndLoc(), Context); - - // First, check if ParentMacroStack is not empty which means we are currently - // dealing with a parent statement which was expanded from a macro. - // If this parent statement was expanded from the same macros as this - // statement, we reduce the initial complexity of this statement to zero. - // This causes that a group of statements that were generated by a single - // macro expansion will only increase the total complexity by one. - // Note: This is not the final complexity of this statement as we still - // add the complexity of the child statements to the complexity value. - if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack && - EndMacroStack == ParentMacroStack)) { - Complexity = 0; - } + // Add a valid clone group to the list of found clone groups. + if (!FilteredGroup.isValid()) + continue; - // Iterate over the Stmts in the StmtSequence and add their complexity values - // to the current complexity value. - if (Seq.holdsSequence()) { - for (const Stmt *S : Seq) { - Complexity += calculateStmtComplexity( - StmtSequence(S, Seq.getContainingDecl()), StartMacroStack); - } - } else { - for (const Stmt *S : Seq.front()->children()) { - Complexity += calculateStmtComplexity( - StmtSequence(S, Seq.getContainingDecl()), StartMacroStack); - } + Result.push_back(FilteredGroup); } - return Complexity; } -void MatchingVariablePatternConstraint::constrain( - std::vector &CloneGroups) { - CloneConstraint::splitCloneGroups( - CloneGroups, [](const StmtSequence &A, const StmtSequence &B) { - VariablePattern PatternA(A); - VariablePattern PatternB(B); - return PatternA.countPatternDifferences(PatternB) == 0; - }); -} +void CloneDetector::findClones(std::vector &Result, + unsigned MinGroupComplexity, + bool CheckPatterns) { + // A shortcut (and necessary for the for-loop later in this function). + if (Sequences.empty()) + return; -void CloneConstraint::splitCloneGroups( - std::vector &CloneGroups, - std::function Compare) { - std::vector Result; - for (auto &HashGroup : CloneGroups) { - // Contains all indexes in HashGroup that were already added to a - // CloneGroup. - std::vector Indexes; - Indexes.resize(HashGroup.size()); - - for (unsigned i = 0; i < HashGroup.size(); ++i) { - // Skip indexes that are already part of a CloneGroup. - if (Indexes[i]) - continue; + // We need to search for groups of StmtSequences with the same hash code to + // create our initial clone groups. By sorting all known StmtSequences by + // their hash value we make sure that StmtSequences with the same hash code + // are grouped together in the Sequences vector. + // Note: We stable sort here because the StmtSequences are added in the order + // in which they appear in the source file. We want to preserve that order + // because we also want to report them in that order in the CloneChecker. + std::stable_sort(Sequences.begin(), Sequences.end(), + [](std::pair LHS, + std::pair RHS) { + return LHS.first.Hash < RHS.first.Hash; + }); + + std::vector CloneGroups; + + // Check for each CloneSignature if its successor has the same hash value. + // We don't check the last CloneSignature as it has no successor. + // Note: The 'size - 1' in the condition is safe because we check for an empty + // Sequences vector at the beginning of this function. + for (unsigned i = 0; i < Sequences.size() - 1; ++i) { + const auto Current = Sequences[i]; + const auto Next = Sequences[i + 1]; + + if (Current.first.Hash != Next.first.Hash) + continue; - // Pick the first unhandled StmtSequence and consider it as the - // beginning - // of a new CloneGroup for now. - // We don't add i to Indexes because we never iterate back. - StmtSequence Prototype = HashGroup[i]; - CloneDetector::CloneGroup PotentialGroup = {Prototype}; - ++Indexes[i]; - - // Check all following StmtSequences for clones. - for (unsigned j = i + 1; j < HashGroup.size(); ++j) { - // Skip indexes that are already part of a CloneGroup. - if (Indexes[j]) - continue; - - // If a following StmtSequence belongs to our CloneGroup, we add it to - // it. - const StmtSequence &Candidate = HashGroup[j]; - - if (!Compare(Prototype, Candidate)) - continue; - - PotentialGroup.push_back(Candidate); - // Make sure we never visit this StmtSequence again. - ++Indexes[j]; + // It's likely that we just found an sequence of CloneSignatures that + // represent a CloneGroup, so we create a new group and start checking and + // adding the CloneSignatures in this sequence. + CloneGroup Group; + Group.Signature = Current.first; + + for (; i < Sequences.size(); ++i) { + const auto &Signature = Sequences[i]; + + // A different hash value means we have reached the end of the sequence. + if (Current.first.Hash != Signature.first.Hash) { + // The current Signature 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 + // the hash of the Current CloneSignature with itself in the 'if' above. + assert(i != 0); + --i; + break; } - // Otherwise, add it to the result and continue searching for more - // groups. - Result.push_back(PotentialGroup); - } - - assert(std::all_of(Indexes.begin(), Indexes.end(), - [](char c) { return c == 1; })); - } - CloneGroups = Result; -} + // Skip CloneSignatures that won't pass the complexity requirement. + if (Signature.first.Complexity < MinGroupComplexity) + continue; -void VariablePattern::addVariableOccurence(const VarDecl *VarDecl, - const Stmt *Mention) { - // First check if we already reference this variable - for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex) { - if (Variables[KindIndex] == VarDecl) { - // If yes, add a new occurence that points to the existing entry in - // the Variables vector. - Occurences.emplace_back(KindIndex, Mention); - return; + Group.Sequences.push_back(Signature.second); } - } - // If this variable wasn't already referenced, add it to the list of - // referenced variables and add a occurence that points to this new entry. - Occurences.emplace_back(Variables.size(), Mention); - Variables.push_back(VarDecl); -} -void VariablePattern::addVariables(const Stmt *S) { - // Sometimes we get a nullptr (such as from IfStmts which often have nullptr - // children). We skip such statements as they don't reference any - // variables. - if (!S) - return; + // There is a chance that we haven't found more than two fitting + // CloneSignature because not enough CloneSignatures passed the complexity + // requirement. As a CloneGroup with less than two members makes no sense, + // we ignore this CloneGroup and won't add it to the result. + if (!Group.isValid()) + continue; - // Check if S is a reference to a variable. If yes, add it to the pattern. - if (auto D = dyn_cast(S)) { - if (auto VD = dyn_cast(D->getDecl()->getCanonicalDecl())) - addVariableOccurence(VD, D); + CloneGroups.push_back(Group); } - // Recursively check all children of the given statement. - for (const Stmt *Child : S->children()) { - addVariables(Child); + // Add every valid clone group that fulfills the complexity requirement. + for (const CloneGroup &Group : CloneGroups) { + createCloneGroups(Result, Group, CheckPatterns); } -} - -unsigned VariablePattern::countPatternDifferences( - const VariablePattern &Other, - VariablePattern::SuspiciousClonePair *FirstMismatch) { - unsigned NumberOfDifferences = 0; - - assert(Other.Occurences.size() == Occurences.size()); - for (unsigned i = 0; i < Occurences.size(); ++i) { - auto ThisOccurence = Occurences[i]; - auto OtherOccurence = Other.Occurences[i]; - if (ThisOccurence.KindID == OtherOccurence.KindID) - continue; - ++NumberOfDifferences; + std::vector IndexesToRemove; - // If FirstMismatch is not a nullptr, we need to store information about - // the first difference between the two patterns. - if (FirstMismatch == nullptr) - continue; + // Compare every group in the result with the rest. If one groups contains + // another group, we only need to return the bigger group. + // Note: This doesn't scale well, so if possible avoid calling any heavy + // function from this loop to minimize the performance impact. + for (unsigned i = 0; i < Result.size(); ++i) { + for (unsigned j = 0; j < Result.size(); ++j) { + // Don't compare a group with itself. + if (i == j) + continue; - // Only proceed if we just found the first difference as we only store - // information about the first difference. - if (NumberOfDifferences != 1) - continue; + if (containsGroup(Result[j], Result[i])) { + IndexesToRemove.push_back(i); + break; + } + } + } - const VarDecl *FirstSuggestion = nullptr; - // If there is a variable available in the list of referenced variables - // which wouldn't break the pattern if it is used in place of the - // current variable, we provide this variable as the suggested fix. - if (OtherOccurence.KindID < Variables.size()) - FirstSuggestion = Variables[OtherOccurence.KindID]; - - // Store information about the first clone. - FirstMismatch->FirstCloneInfo = - VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo( - Variables[ThisOccurence.KindID], ThisOccurence.Mention, - FirstSuggestion); - - // Same as above but with the other clone. We do this for both clones as - // we don't know which clone is the one containing the unintended - // pattern error. - const VarDecl *SecondSuggestion = nullptr; - if (ThisOccurence.KindID < Other.Variables.size()) - SecondSuggestion = Other.Variables[ThisOccurence.KindID]; - - // Store information about the second clone. - FirstMismatch->SecondCloneInfo = - VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo( - Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention, - SecondSuggestion); - - // SuspiciousClonePair guarantees that the first clone always has a - // suggested variable associated with it. As we know that one of the two - // clones in the pair always has suggestion, we swap the two clones - // in case the first clone has no suggested variable which means that - // the second clone has a suggested variable and should be first. - if (!FirstMismatch->FirstCloneInfo.Suggestion) - std::swap(FirstMismatch->FirstCloneInfo, FirstMismatch->SecondCloneInfo); - - // This ensures that we always have at least one suggestion in a pair. - assert(FirstMismatch->FirstCloneInfo.Suggestion); + // Erasing a list of indexes from the vector should be done with decreasing + // indexes. As IndexesToRemove is constructed with increasing values, we just + // reverse iterate over it to get the desired order. + for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); ++I) { + Result.erase(Result.begin() + *I); } +} - return NumberOfDifferences; +void CloneDetector::findSuspiciousClones( + std::vector &Result, + unsigned MinGroupComplexity) { + std::vector Clones; + // Reuse the normal search for clones but specify that the clone groups don't + // need to have a common referenced variable pattern so that we can manually + // search for the kind of pattern errors this function is supposed to find. + findClones(Clones, MinGroupComplexity, false); + + for (const CloneGroup &Group : Clones) { + for (unsigned i = 0; i < Group.Sequences.size(); ++i) { + VariablePattern PatternA(Group.Sequences[i]); + + for (unsigned j = i + 1; j < Group.Sequences.size(); ++j) { + VariablePattern PatternB(Group.Sequences[j]); + + CloneDetector::SuspiciousClonePair ClonePair; + // For now, we only report clones which break the variable pattern just + // once because multiple differences in a pattern are an indicator that + // those differences are maybe intended (e.g. because it's actually + // a different algorithm). + // TODO: In very big clones even multiple variables can be unintended, + // so replacing this number with a percentage could better handle such + // cases. On the other hand it could increase the false-positive rate + // for all clones if the percentage is too high. + if (PatternA.countPatternDifferences(PatternB, &ClonePair) == 1) { + Result.push_back(ClonePair); + break; + } + } + } + } } diff --git a/lib/StaticAnalyzer/Checkers/CloneChecker.cpp b/lib/StaticAnalyzer/Checkers/CloneChecker.cpp index 1885b0e392..6fa5732d10 100644 --- a/lib/StaticAnalyzer/Checkers/CloneChecker.cpp +++ b/lib/StaticAnalyzer/Checkers/CloneChecker.cpp @@ -38,15 +38,14 @@ public: void checkEndOfTranslationUnit(const TranslationUnitDecl *TU, AnalysisManager &Mgr, BugReporter &BR) const; - /// Reports all clones to the user. + /// \brief Reports all clones to the user. void reportClones(BugReporter &BR, AnalysisManager &Mgr, - std::vector &CloneGroups) const; + int MinComplexity) const; - /// Reports only suspicious clones to the user along with informaton - /// that explain why they are suspicious. - void reportSuspiciousClones( - BugReporter &BR, AnalysisManager &Mgr, - std::vector &CloneGroups) const; + /// \brief Reports only suspicious clones to the user along with informaton + /// that explain why they are suspicious. + void reportSuspiciousClones(BugReporter &BR, AnalysisManager &Mgr, + int MinComplexity) const; }; } // end anonymous namespace @@ -73,30 +72,11 @@ void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU, bool ReportNormalClones = Mgr.getAnalyzerOptions().getBooleanOption( "ReportNormalClones", true, this); - // Let the CloneDetector create a list of clones from all the analyzed - // statements. We don't filter for matching variable patterns at this point - // because reportSuspiciousClones() wants to search them for errors. - std::vector AllCloneGroups; - - Detector.findClones(AllCloneGroups, RecursiveCloneTypeIIConstraint(), - MinComplexityConstraint(MinComplexity), - MinGroupSizeConstraint(2), OnlyLargestCloneConstraint()); - if (ReportSuspiciousClones) - reportSuspiciousClones(BR, Mgr, AllCloneGroups); - - // We are done for this translation unit unless we also need to report normal - // clones. - if (!ReportNormalClones) - return; + reportSuspiciousClones(BR, Mgr, MinComplexity); - // Now that the suspicious clone detector has checked for pattern errors, - // we also filter all clones who don't have matching patterns - CloneDetector::constrainClones(AllCloneGroups, - MatchingVariablePatternConstraint(), - MinGroupSizeConstraint(2)); - - reportClones(BR, Mgr, AllCloneGroups); + if (ReportNormalClones) + reportClones(BR, Mgr, MinComplexity); } static PathDiagnosticLocation makeLocation(const StmtSequence &S, @@ -107,55 +87,37 @@ static PathDiagnosticLocation makeLocation(const StmtSequence &S, Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl())); } -void CloneChecker::reportClones( - BugReporter &BR, AnalysisManager &Mgr, - std::vector &CloneGroups) const { +void CloneChecker::reportClones(BugReporter &BR, AnalysisManager &Mgr, + int MinComplexity) const { + + std::vector CloneGroups; + Detector.findClones(CloneGroups, MinComplexity); if (!BT_Exact) BT_Exact.reset(new BugType(this, "Exact code clone", "Code clone")); - for (const CloneDetector::CloneGroup &Group : CloneGroups) { + for (CloneDetector::CloneGroup &Group : CloneGroups) { // We group the clones by printing the first as a warning and all others // as a note. - auto R = llvm::make_unique(*BT_Exact, "Duplicate code detected", - makeLocation(Group.front(), Mgr)); - R->addRange(Group.front().getSourceRange()); - - for (unsigned i = 1; i < Group.size(); ++i) - R->addNote("Similar code here", makeLocation(Group[i], Mgr), - Group[i].getSourceRange()); + auto R = llvm::make_unique( + *BT_Exact, "Duplicate code detected", + makeLocation(Group.Sequences.front(), Mgr)); + R->addRange(Group.Sequences.front().getSourceRange()); + + for (unsigned i = 1; i < Group.Sequences.size(); ++i) + R->addNote("Similar code here", + makeLocation(Group.Sequences[i], Mgr), + Group.Sequences[i].getSourceRange()); BR.emitReport(std::move(R)); } } -void CloneChecker::reportSuspiciousClones( - BugReporter &BR, AnalysisManager &Mgr, - std::vector &CloneGroups) const { - std::vector Pairs; - - for (const CloneDetector::CloneGroup &Group : CloneGroups) { - for (unsigned i = 0; i < Group.size(); ++i) { - VariablePattern PatternA(Group[i]); - - for (unsigned j = i + 1; j < Group.size(); ++j) { - VariablePattern PatternB(Group[j]); - - VariablePattern::SuspiciousClonePair ClonePair; - // For now, we only report clones which break the variable pattern just - // once because multiple differences in a pattern are an indicator that - // those differences are maybe intended (e.g. because it's actually a - // different algorithm). - // FIXME: In very big clones even multiple variables can be unintended, - // so replacing this number with a percentage could better handle such - // cases. On the other hand it could increase the false-positive rate - // for all clones if the percentage is too high. - if (PatternA.countPatternDifferences(PatternB, &ClonePair) == 1) { - Pairs.push_back(ClonePair); - break; - } - } - } - } +void CloneChecker::reportSuspiciousClones(BugReporter &BR, + AnalysisManager &Mgr, + int MinComplexity) const { + + std::vector Clones; + Detector.findSuspiciousClones(Clones, MinComplexity); if (!BT_Suspicious) BT_Suspicious.reset( @@ -166,7 +128,7 @@ void CloneChecker::reportSuspiciousClones( AnalysisDeclContext *ADC = Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl()); - for (VariablePattern::SuspiciousClonePair &Pair : Pairs) { + for (CloneDetector::SuspiciousClonePair &Pair : Clones) { // FIXME: We are ignoring the suggestions currently, because they are // only 50% accurate (even if the second suggestion is unavailable), // which may confuse the user. diff --git a/unittests/Analysis/CMakeLists.txt b/unittests/Analysis/CMakeLists.txt index 62db8f652e..926f586be3 100644 --- a/unittests/Analysis/CMakeLists.txt +++ b/unittests/Analysis/CMakeLists.txt @@ -2,12 +2,11 @@ set(LLVM_LINK_COMPONENTS Support ) -add_clang_unittest(ClangAnalysisTests +add_clang_unittest(CFGTests CFGTest.cpp - CloneDetectionTest.cpp ) -target_link_libraries(ClangAnalysisTests +target_link_libraries(CFGTests clangAnalysis clangAST clangASTMatchers diff --git a/unittests/Analysis/CloneDetectionTest.cpp b/unittests/Analysis/CloneDetectionTest.cpp deleted file mode 100644 index d9bab9ea96..0000000000 --- a/unittests/Analysis/CloneDetectionTest.cpp +++ /dev/null @@ -1,110 +0,0 @@ -//===- unittests/Analysis/CloneDetectionTest.cpp - Clone detection tests --===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "clang/AST/RecursiveASTVisitor.h" -#include "clang/Analysis/CloneDetection.h" -#include "clang/Tooling/Tooling.h" -#include "gtest/gtest.h" - -namespace clang { -namespace analysis { -namespace { - -class CloneDetectionVisitor - : public RecursiveASTVisitor { - - CloneDetector &Detector; - -public: - explicit CloneDetectionVisitor(CloneDetector &D) : Detector(D) {} - - bool VisitFunctionDecl(FunctionDecl *D) { - Detector.analyzeCodeBody(D); - return true; - } -}; - -/// Example constraint for testing purposes. -/// Filters out all statements that are in a function which name starts with -/// "bar". -class NoBarFunctionConstraint { -public: - void constrain(std::vector &CloneGroups) { - CloneConstraint::splitCloneGroups( - CloneGroups, [](const StmtSequence &A, const StmtSequence &B) { - // Check if one of the sequences is in a function which name starts - // with "bar". - for (const StmtSequence &Arg : {A, B}) { - if (const auto *D = - dyn_cast(Arg.getContainingDecl())) { - if (D->getNameAsString().find("bar") == 0) - return false; - } - } - return true; - }); - } -}; - -TEST(CloneDetector, NoPostOrderTraversal) { - auto ASTUnit = - clang::tooling::buildASTFromCode("void foo1(int &a1) { a1++; }\n" - "void foo2(int &a2) { a2++; }\n" - "void bar1(int &a3) { a3++; }\n" - "void bar2(int &a4) { a4++; }\n"); - auto TU = ASTUnit->getASTContext().getTranslationUnitDecl(); - - CloneDetector Detector; - // Push all the function bodies into the detector. - CloneDetectionVisitor Visitor(Detector); - Visitor.TraverseTranslationUnitDecl(TU); - - // Find clones with the usual settings, but but we want to filter out - // all statements from functions which names start with "bar". - std::vector CloneGroups; - Detector.findClones(CloneGroups, NoBarFunctionConstraint(), - RecursiveCloneTypeIIConstraint(), - MinComplexityConstraint(2), MinGroupSizeConstraint(2), - OnlyLargestCloneConstraint()); - - ASSERT_EQ(CloneGroups.size(), 1u); - ASSERT_EQ(CloneGroups.front().size(), 2u); - - for (auto &Clone : CloneGroups.front()) { - const auto ND = dyn_cast(Clone.getContainingDecl()); - ASSERT_TRUE(ND != nullptr); - // Check that no function name starting with "bar" is in the results... - ASSERT_TRUE(ND->getNameAsString().find("bar") != 0); - } - - // Retry above's example without the filter... - CloneGroups.clear(); - - Detector.findClones(CloneGroups, RecursiveCloneTypeIIConstraint(), - MinComplexityConstraint(2), MinGroupSizeConstraint(2), - OnlyLargestCloneConstraint()); - ASSERT_EQ(CloneGroups.size(), 1u); - ASSERT_EQ(CloneGroups.front().size(), 4u); - - // Count how many functions with the bar prefix we have in the results. - int FoundFunctionsWithBarPrefix = 0; - for (auto &Clone : CloneGroups.front()) { - const auto ND = dyn_cast(Clone.getContainingDecl()); - ASSERT_TRUE(ND != nullptr); - // This time check that we picked up the bar functions from above - if (ND->getNameAsString().find("bar") == 0) { - FoundFunctionsWithBarPrefix++; - } - } - // We should have found the two functions bar1 and bar2. - ASSERT_EQ(FoundFunctionsWithBarPrefix, 2); -} -} // namespace -} // namespace analysis -} // namespace clang -- 2.40.0