Index: include/clang/Analysis/CloneDetection.h =================================================================== --- include/clang/Analysis/CloneDetection.h +++ include/clang/Analysis/CloneDetection.h @@ -16,9 +16,7 @@ #define LLVM_CLANG_AST_CLONEDETECTION_H #include "clang/Basic/SourceLocation.h" -#include "llvm/ADT/Hashing.h" -#include "llvm/ADT/StringMap.h" - +#include "llvm/ADT/SmallVector.h" #include namespace clang { @@ -29,7 +27,7 @@ class ASTContext; class CompoundStmt; -/// \brief Identifies a list of statements. +/// 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. @@ -39,8 +37,8 @@ /// Stmt, then S is a pointer to this Stmt. const Stmt *S; - /// The related ASTContext for S. - ASTContext *Context; + /// The declaration that contains the statements. + const Decl *D; /// If EndIndex is non-zero, then S is a CompoundStmt and this StmtSequence /// instance is representing the CompoundStmt children inside the array @@ -49,7 +47,7 @@ unsigned EndIndex; public: - /// \brief Constructs a StmtSequence holding multiple statements. + /// 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 @@ -57,20 +55,20 @@ /// 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 Context The ASTContext for the given CompoundStmt. + /// \param Decl The Decl containing this Stmt. /// \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, ASTContext &Context, - unsigned StartIndex, unsigned EndIndex); + StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex, + unsigned EndIndex); - /// \brief Constructs a StmtSequence holding a single statement. + /// Constructs a StmtSequence holding a single statement. /// /// \param Stmt An arbitrary Stmt. - /// \param Context The ASTContext for the given Stmt. - StmtSequence(const Stmt *Stmt, ASTContext &Context); + /// \param Decl The Decl containing this Stmt. + StmtSequence(const Stmt *Stmt, const Decl *D); - /// \brief Constructs an empty StmtSequence. + /// Constructs an empty StmtSequence. StmtSequence(); typedef const Stmt *const *iterator; @@ -110,9 +108,12 @@ bool empty() const { return size() == 0; } /// Returns the related ASTContext for the stored Stmts. - ASTContext &getASTContext() const { - assert(Context); - return *Context; + ASTContext &getASTContext() const; + + /// Returns the declaration that contains the stored Stmts. + const Decl *getContainingDecl() const { + assert(D); + return D; } /// Returns true if this objects holds a list of statements. @@ -150,106 +151,214 @@ bool contains(const StmtSequence &Other) const; }; -/// \brief Searches for clones in source code. +/// Searches for similar subtrees in the AST. /// -/// 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 . +/// 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. /// /// 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: - 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) {} - }; + /// A collection of StmtSequences that share an arbitrary property. + typedef llvm::SmallVector CloneGroup; - /// 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; + /// Generates and stores search data for all statements in the body of + /// the given Decl. + void analyzeCodeBody(const Decl *D); - CloneGroup() {} + /// 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(const StmtSequence &Seq, CloneSignature Signature) - : Signature(Signature) { - Sequences.push_back(Seq); - } + /// 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...); + } - /// \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; + /// 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); } - }; - /// \brief Generates and stores search data for all statements in the body of - /// the given Decl. - void analyzeCodeBody(const Decl *D); + Result.push_back(AllClones); - /// \brief Stores the CloneSignature to allow future querying. - void add(const StmtSequence &S, const CloneSignature &Signature); + constrainClones(Result, ConstraintList...); + } - /// \brief Searches the provided statements for clones. +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. /// - /// \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. + /// 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) {} + }; + + /// 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); + + /// Adds each referenced variable from the given statement. + void addVariables(const Stmt *S); + +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. struct SuspiciousClonePair { - /// \brief Utility class holding the relevant information about a single - /// clone in this pair. + /// 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; @@ -270,17 +379,37 @@ SuspiciousCloneInfo SecondCloneInfo; }; - /// \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); + /// 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); +}; -private: - /// Stores all encountered StmtSequences alongside their CloneSignature. - std::vector> Sequences; +/// Ensures that all clones reference variables in the same pattern. +struct MatchingVariablePatternConstraint { + void constrain(std::vector &CloneGroups); }; } // end namespace clang Index: lib/Analysis/CloneDetection.cpp =================================================================== --- lib/Analysis/CloneDetection.cpp +++ lib/Analysis/CloneDetection.cpp @@ -1,4 +1,4 @@ -//===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===// +//===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -24,27 +24,27 @@ using namespace clang; -StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context, +StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex, unsigned EndIndex) - : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) { + : S(Stmt), D(D), 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, ASTContext &Context) - : S(Stmt), Context(&Context), StartIndex(0), EndIndex(0) {} +StmtSequence::StmtSequence(const Stmt *Stmt, const Decl *D) + : S(Stmt), D(D), StartIndex(0), EndIndex(0) {} StmtSequence::StmtSequence() - : S(nullptr), Context(nullptr), StartIndex(0), EndIndex(0) {} + : S(nullptr), D(nullptr), StartIndex(0), EndIndex(0) {} bool StmtSequence::contains(const StmtSequence &Other) const { // If both sequences reside in different translation units, they can never // contain each other. - if (Context != Other.Context) + if (D != Other.D) return false; - const SourceManager &SM = Context->getSourceManager(); + const SourceManager &SM = getASTContext().getSourceManager(); // Otherwise check if the start and end locations of the current sequence // surround the other sequence. @@ -76,6 +76,11 @@ return CS->body_begin() + EndIndex; } +ASTContext &StmtSequence::getASTContext() const { + assert(D); + return D->getASTContext(); +} + SourceLocation StmtSequence::getStartLoc() const { return front()->getLocStart(); } @@ -86,168 +91,8 @@ return SourceRange(getStartLoc(), getEndLoc()); } -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. +/// 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(), @@ -258,8 +103,8 @@ MacroStack << " "; } -/// \brief Returns a string that represents all macro expansions that -/// expanded into the given SourceLocation. +/// 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. @@ -279,7 +124,9 @@ } namespace { -/// \brief Collects the data of a single Stmt. +typedef unsigned DataPiece; + +/// 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 @@ -292,11 +139,11 @@ class StmtDataCollector : public ConstStmtVisitor> { ASTContext &Context; - /// \brief The data sink to which all data is forwarded. + /// The data sink to which all data is forwarded. T &DataConsumer; public: - /// \brief Collects data of the given Stmt. + /// 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. @@ -307,7 +154,7 @@ // Below are utility methods for appending different data to the vector. - void addData(CloneDetector::DataPiece Integer) { + void addData(DataPiece Integer) { DataConsumer.update( StringRef(reinterpret_cast(&Integer), sizeof(Integer))); } @@ -425,7 +272,7 @@ }) 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()); @@ -454,199 +301,131 @@ }; } // end anonymous namespace -namespace { -/// Generates CloneSignatures for a set of statements and stores the results in -/// a CloneDetector object. -class CloneSignatureGenerator { +void CloneDetector::analyzeCodeBody(const Decl *D) { + assert(D); + assert(D->hasBody()); - CloneDetector &CD; - ASTContext &Context; + Sequences.push_back(StmtSequence(D->getBody(), D)); +} - /// \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; - } +/// 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; +} - // 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); +/// 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; - // 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; + for (StmtSequence &Stmt : Group) { + if (!containsAnyInGroup(Stmt, OtherGroup)) + return false; + } + return true; +} - // 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); +void OnlyLargestCloneConstraint::constrain( + std::vector &Result) { + std::vector IndexesToRemove; - // 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))); + // 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; - // 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); + if (containsGroup(Result[j], Result[i])) { + IndexesToRemove.push_back(i); + break; + } } + } - // 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); + // 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); + } +} - // Create the final hash code for the current signature. - llvm::MD5::MD5Result HashResult; - Hash.final(HashResult); +static size_t createHash(llvm::MD5 &Hash) { + size_t 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))); + // Create the final hash code for the current Stmt. + llvm::MD5::MD5Result HashResult; + Hash.final(HashResult); - // Save the signature for the current statement in the CloneDetector object. - CD.add(StmtSequence(S, Context), Signature); + // 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))); - return Signature; - } + return HashCode; +} - /// \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) { +size_t RecursiveCloneTypeIIConstraint::saveHash( + const Stmt *S, const Decl *D, + std::vector> &StmtsByHash) { + llvm::MD5 Hash; + ASTContext &Context = D->getASTContext(); - // FIXME: This function has quadratic runtime right now. Check if skipping - // this function for too long CompoundStmts is an option. + StmtDataCollector(S, Context, Hash); - // The length of the sub-sequence. We don't need to handle sequences with - // the length 1 as they are already handled in CollectData(). + auto CS = dyn_cast(S); + SmallVector ChildHashes; + + 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); + } + + if (CS) { 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) { - // Create an empty signature and add the signatures of all selected - // child statements to it. - CloneDetector::CloneSignature SubSignature; - llvm::MD5 SubHash; - + llvm::MD5 Hash; for (unsigned i = Pos; i < Pos + Length; ++i) { - SubSignature.Complexity += ChildSignatures[i].Complexity; - size_t ChildHash = ChildSignatures[i].Hash; - - SubHash.update(StringRef(reinterpret_cast(&ChildHash), + size_t ChildHash = ChildHashes[i]; + Hash.update(StringRef(reinterpret_cast(&ChildHash), sizeof(ChildHash))); } - - // 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); + StmtsByHash.push_back(std::make_pair( + createHash(Hash), StmtSequence(CS, D, Pos, Pos + Length))); } } } -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)); + size_t HashCode = createHash(Hash); + StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D))); + return HashCode; } namespace { -/// \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. +/// Wrapper around FoldingSetNodeID that it can be used as the template +/// argument of the StmtDataCollector. class FoldingSetNodeIDWrapper { llvm::FoldingSetNodeID &FS; @@ -658,8 +437,8 @@ }; } // end anonymous namespace -/// \brief Writes the relevant data from all statements and child statements -/// in the given StmtSequence into the given FoldingSetNodeID. +/// 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) { @@ -670,13 +449,13 @@ if (!Child) continue; - CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()), + CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()), OutputData); } } } -/// \brief Returns true if both sequences are clones of each other. +/// 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 @@ -693,202 +472,272 @@ return DataLHS == DataRHS; } -/// \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; - } +void RecursiveCloneTypeIIConstraint::constrain( + std::vector &Sequences) { + // FIXME: Maybe we can do this in-place and don't need this additional vector. + std::vector Result; - // 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; - } + 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; - // We didn't found a matching variable pattern, so we continue with the - // next sequence. - ++I; + // Generate hash codes for all children of S and save them in StmtsByHash. + for (const StmtSequence &S : Group) { + saveHash(S.front(), S.getContainingDecl(), StmtsByHash); } - // Add a valid clone group to the list of found clone groups. - if (!FilteredGroup.isValid()) - 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); + } - Result.push_back(FilteredGroup); + // We created a new clone group with matching hash codes and move it to + // the result vector. + Result.push_back(NewGroup); + } } + // Sequences is the output parameter, so we copy our result into it. + Sequences = Result; } -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; +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; + } - // 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; + // 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); + } + } + return Complexity; +} - // 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; - } +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; + }); +} - // Skip CloneSignatures that won't pass the complexity requirement. - if (Signature.first.Complexity < MinGroupComplexity) +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; - Group.Sequences.push_back(Signature.second); - } + // 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]; + } - // 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; + // Otherwise, add it to the result and continue searching for more + // groups. + Result.push_back(PotentialGroup); + } - CloneGroups.push_back(Group); + assert(std::all_of(Indexes.begin(), Indexes.end(), + [](char c) { return c == 1; })); } + CloneGroups = Result; +} - // Add every valid clone group that fulfills the complexity requirement. - for (const CloneGroup &Group : CloneGroups) { - createCloneGroups(Result, Group, CheckPatterns); +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; + } } + // 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); +} - std::vector IndexesToRemove; - - // 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; +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; - if (containsGroup(Result[j], Result[i])) { - IndexesToRemove.push_back(i); - break; - } - } + // 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); } - // 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); + // Recursively check all children of the given statement. + for (const Stmt *Child : S->children()) { + addVariables(Child); } } -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; - } - } - } +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; + + // 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 = + 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); } + + return NumberOfDifferences; } Index: lib/StaticAnalyzer/Checkers/CloneChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/CloneChecker.cpp +++ lib/StaticAnalyzer/Checkers/CloneChecker.cpp @@ -38,14 +38,15 @@ void checkEndOfTranslationUnit(const TranslationUnitDecl *TU, AnalysisManager &Mgr, BugReporter &BR) const; - /// \brief Reports all clones to the user. + /// Reports all clones to the user. void reportClones(BugReporter &BR, AnalysisManager &Mgr, - int MinComplexity) const; + 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; + /// 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; }; } // end anonymous namespace @@ -72,11 +73,30 @@ 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, MinComplexity); + reportSuspiciousClones(BR, Mgr, AllCloneGroups); + + // We are done for this translation unit unless we also need to report normal + // clones. + if (!ReportNormalClones) + return; - if (ReportNormalClones) - reportClones(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); } static PathDiagnosticLocation makeLocation(const StmtSequence &S, @@ -87,37 +107,55 @@ Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl())); } -void CloneChecker::reportClones(BugReporter &BR, AnalysisManager &Mgr, - int MinComplexity) const { - - std::vector CloneGroups; - Detector.findClones(CloneGroups, MinComplexity); +void CloneChecker::reportClones( + BugReporter &BR, AnalysisManager &Mgr, + std::vector &CloneGroups) const { if (!BT_Exact) BT_Exact.reset(new BugType(this, "Exact code clone", "Code clone")); - for (CloneDetector::CloneGroup &Group : CloneGroups) { + for (const 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.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()); + 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()); BR.emitReport(std::move(R)); } } -void CloneChecker::reportSuspiciousClones(BugReporter &BR, - AnalysisManager &Mgr, - int MinComplexity) const { - - std::vector Clones; - Detector.findSuspiciousClones(Clones, MinComplexity); +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; + } + } + } + } if (!BT_Suspicious) BT_Suspicious.reset( @@ -128,7 +166,7 @@ AnalysisDeclContext *ADC = Mgr.getAnalysisDeclContext(ACtx.getTranslationUnitDecl()); - for (CloneDetector::SuspiciousClonePair &Pair : Clones) { + for (VariablePattern::SuspiciousClonePair &Pair : Pairs) { // 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. Index: unittests/Analysis/CMakeLists.txt =================================================================== --- unittests/Analysis/CMakeLists.txt +++ unittests/Analysis/CMakeLists.txt @@ -2,11 +2,12 @@ Support ) -add_clang_unittest(CFGTests +add_clang_unittest(ClangAnalysisTests CFGTest.cpp + CloneDetectionTest.cpp ) -target_link_libraries(CFGTests +target_link_libraries(ClangAnalysisTests clangAnalysis clangAST clangASTMatchers Index: unittests/Analysis/CloneDetectionTest.cpp =================================================================== --- /dev/null +++ unittests/Analysis/CloneDetectionTest.cpp @@ -0,0 +1,111 @@ +//===- 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