1 //===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// This file implements classes for searching and anlyzing source code clones.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Analysis/CloneDetection.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/RecursiveASTVisitor.h"
18 #include "clang/AST/Stmt.h"
19 #include "clang/AST/StmtVisitor.h"
20 #include "clang/Lex/Lexer.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/Support/MD5.h"
23 #include "llvm/Support/raw_ostream.h"
25 using namespace clang;
27 StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context,
28 unsigned StartIndex, unsigned EndIndex)
29 : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) {
30 assert(Stmt && "Stmt must not be a nullptr");
31 assert(StartIndex < EndIndex && "Given array should not be empty");
32 assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt");
35 StmtSequence::StmtSequence(const Stmt *Stmt, ASTContext &Context)
36 : S(Stmt), Context(&Context), StartIndex(0), EndIndex(0) {}
38 StmtSequence::StmtSequence()
39 : S(nullptr), Context(nullptr), StartIndex(0), EndIndex(0) {}
41 bool StmtSequence::contains(const StmtSequence &Other) const {
42 // If both sequences reside in different translation units, they can never
43 // contain each other.
44 if (Context != Other.Context)
47 const SourceManager &SM = Context->getSourceManager();
49 // Otherwise check if the start and end locations of the current sequence
50 // surround the other sequence.
51 bool StartIsInBounds =
52 SM.isBeforeInTranslationUnit(getStartLoc(), Other.getStartLoc()) ||
53 getStartLoc() == Other.getStartLoc();
58 SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) ||
59 Other.getEndLoc() == getEndLoc();
63 StmtSequence::iterator StmtSequence::begin() const {
64 if (!holdsSequence()) {
67 auto CS = cast<CompoundStmt>(S);
68 return CS->body_begin() + StartIndex;
71 StmtSequence::iterator StmtSequence::end() const {
72 if (!holdsSequence()) {
73 return reinterpret_cast<StmtSequence::iterator>(&S) + 1;
75 auto CS = cast<CompoundStmt>(S);
76 return CS->body_begin() + EndIndex;
79 SourceLocation StmtSequence::getStartLoc() const {
80 return front()->getLocStart();
83 SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
85 SourceRange StmtSequence::getSourceRange() const {
86 return SourceRange(getStartLoc(), getEndLoc());
91 /// \brief Analyzes the pattern of the referenced variables in a statement.
92 class VariablePattern {
94 /// \brief Describes an occurence of a variable reference in a statement.
95 struct VariableOccurence {
96 /// The index of the associated VarDecl in the Variables vector.
98 /// The statement in the code where the variable was referenced.
101 VariableOccurence(size_t KindID, const Stmt *Mention)
102 : KindID(KindID), Mention(Mention) {}
105 /// All occurences of referenced variables in the order of appearance.
106 std::vector<VariableOccurence> Occurences;
107 /// List of referenced variables in the order of appearance.
108 /// Every item in this list is unique.
109 std::vector<const VarDecl *> Variables;
111 /// \brief Adds a new variable referenced to this pattern.
112 /// \param VarDecl The declaration of the variable that is referenced.
113 /// \param Mention The SourceRange where this variable is referenced.
114 void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention) {
115 // First check if we already reference this variable
116 for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex) {
117 if (Variables[KindIndex] == VarDecl) {
118 // If yes, add a new occurence that points to the existing entry in
119 // the Variables vector.
120 Occurences.emplace_back(KindIndex, Mention);
124 // If this variable wasn't already referenced, add it to the list of
125 // referenced variables and add a occurence that points to this new entry.
126 Occurences.emplace_back(Variables.size(), Mention);
127 Variables.push_back(VarDecl);
130 /// \brief Adds each referenced variable from the given statement.
131 void addVariables(const Stmt *S) {
132 // Sometimes we get a nullptr (such as from IfStmts which often have nullptr
133 // children). We skip such statements as they don't reference any
138 // Check if S is a reference to a variable. If yes, add it to the pattern.
139 if (auto D = dyn_cast<DeclRefExpr>(S)) {
140 if (auto VD = dyn_cast<VarDecl>(D->getDecl()->getCanonicalDecl()))
141 addVariableOccurence(VD, D);
144 // Recursively check all children of the given statement.
145 for (const Stmt *Child : S->children()) {
151 /// \brief Creates an VariablePattern object with information about the given
153 VariablePattern(const StmtSequence &Sequence) {
154 for (const Stmt *S : Sequence)
158 /// \brief Counts the differences between this pattern and the given one.
159 /// \param Other The given VariablePattern to compare with.
160 /// \param FirstMismatch Output parameter that will be filled with information
161 /// about the first difference between the two patterns. This parameter
162 /// can be a nullptr, in which case it will be ignored.
163 /// \return Returns the number of differences between the pattern this object
164 /// is following and the given VariablePattern.
166 /// For example, the following statements all have the same pattern and this
167 /// function would return zero:
169 /// if (a < b) return a; return b;
170 /// if (x < y) return x; return y;
171 /// if (u2 < u1) return u2; return u1;
173 /// But the following statement has a different pattern (note the changed
174 /// variables in the return statements) and would have two differences when
175 /// compared with one of the statements above.
177 /// if (a < b) return b; return a;
179 /// This function should only be called if the related statements of the given
180 /// pattern and the statements of this objects are clones of each other.
181 unsigned countPatternDifferences(
182 const VariablePattern &Other,
183 CloneDetector::SuspiciousClonePair *FirstMismatch = nullptr) {
184 unsigned NumberOfDifferences = 0;
186 assert(Other.Occurences.size() == Occurences.size());
187 for (unsigned i = 0; i < Occurences.size(); ++i) {
188 auto ThisOccurence = Occurences[i];
189 auto OtherOccurence = Other.Occurences[i];
190 if (ThisOccurence.KindID == OtherOccurence.KindID)
193 ++NumberOfDifferences;
195 // If FirstMismatch is not a nullptr, we need to store information about
196 // the first difference between the two patterns.
197 if (FirstMismatch == nullptr)
200 // Only proceed if we just found the first difference as we only store
201 // information about the first difference.
202 if (NumberOfDifferences != 1)
205 const VarDecl *FirstSuggestion = nullptr;
206 // If there is a variable available in the list of referenced variables
207 // which wouldn't break the pattern if it is used in place of the
208 // current variable, we provide this variable as the suggested fix.
209 if (OtherOccurence.KindID < Variables.size())
210 FirstSuggestion = Variables[OtherOccurence.KindID];
212 // Store information about the first clone.
213 FirstMismatch->FirstCloneInfo =
214 CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo(
215 Variables[ThisOccurence.KindID], ThisOccurence.Mention,
218 // Same as above but with the other clone. We do this for both clones as
219 // we don't know which clone is the one containing the unintended
221 const VarDecl *SecondSuggestion = nullptr;
222 if (ThisOccurence.KindID < Other.Variables.size())
223 SecondSuggestion = Other.Variables[ThisOccurence.KindID];
225 // Store information about the second clone.
226 FirstMismatch->SecondCloneInfo =
227 CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo(
228 Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention,
231 // SuspiciousClonePair guarantees that the first clone always has a
232 // suggested variable associated with it. As we know that one of the two
233 // clones in the pair always has suggestion, we swap the two clones
234 // in case the first clone has no suggested variable which means that
235 // the second clone has a suggested variable and should be first.
236 if (!FirstMismatch->FirstCloneInfo.Suggestion)
237 std::swap(FirstMismatch->FirstCloneInfo,
238 FirstMismatch->SecondCloneInfo);
240 // This ensures that we always have at least one suggestion in a pair.
241 assert(FirstMismatch->FirstCloneInfo.Suggestion);
244 return NumberOfDifferences;
249 /// \brief Prints the macro name that contains the given SourceLocation into
250 /// the given raw_string_ostream.
251 static void printMacroName(llvm::raw_string_ostream &MacroStack,
252 ASTContext &Context, SourceLocation Loc) {
253 MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(),
254 Context.getLangOpts());
256 // Add an empty space at the end as a padding to prevent
257 // that macro names concatenate to the names of other macros.
261 /// \brief Returns a string that represents all macro expansions that
262 /// expanded into the given SourceLocation.
264 /// If 'getMacroStack(A) == getMacroStack(B)' is true, then the SourceLocations
265 /// A and B are expanded from the same macros in the same order.
266 static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
267 std::string MacroStack;
268 llvm::raw_string_ostream MacroStackStream(MacroStack);
269 SourceManager &SM = Context.getSourceManager();
271 // Iterate over all macros that expanded into the given SourceLocation.
272 while (Loc.isMacroID()) {
273 // Add the macro name to the stream.
274 printMacroName(MacroStackStream, Context, Loc);
275 Loc = SM.getImmediateMacroCallerLoc(Loc);
277 MacroStackStream.flush();
282 /// \brief Collects the data of a single Stmt.
284 /// This class defines what a code clone is: If it collects for two statements
285 /// the same data, then those two statements are considered to be clones of each
288 /// All collected data is forwarded to the given data consumer of the type T.
289 /// The data consumer class needs to provide a member method with the signature:
290 /// update(StringRef Str)
291 template <typename T>
292 class StmtDataCollector : public ConstStmtVisitor<StmtDataCollector<T>> {
295 /// \brief The data sink to which all data is forwarded.
299 /// \brief Collects data of the given Stmt.
300 /// \param S The given statement.
301 /// \param Context The ASTContext of S.
302 /// \param DataConsumer The data sink to which all data is forwarded.
303 StmtDataCollector(const Stmt *S, ASTContext &Context, T &DataConsumer)
304 : Context(Context), DataConsumer(DataConsumer) {
308 // Below are utility methods for appending different data to the vector.
310 void addData(CloneDetector::DataPiece Integer) {
312 StringRef(reinterpret_cast<char *>(&Integer), sizeof(Integer)));
315 void addData(llvm::StringRef Str) { DataConsumer.update(Str); }
317 void addData(const QualType &QT) { addData(QT.getAsString()); }
319 // The functions below collect the class specific data of each Stmt subclass.
321 // Utility macro for defining a visit method for a given class. This method
322 // calls back to the ConstStmtVisitor to visit all parent classes.
323 #define DEF_ADD_DATA(CLASS, CODE) \
324 void Visit##CLASS(const CLASS *S) { \
326 ConstStmtVisitor<StmtDataCollector>::Visit##CLASS(S); \
330 addData(S->getStmtClass());
331 // This ensures that macro generated code isn't identical to macro-generated
333 addData(getMacroStack(S->getLocStart(), Context));
334 addData(getMacroStack(S->getLocEnd(), Context));
336 DEF_ADD_DATA(Expr, { addData(S->getType()); })
338 //--- Builtin functionality ----------------------------------------------//
339 DEF_ADD_DATA(ArrayTypeTraitExpr, { addData(S->getTrait()); })
340 DEF_ADD_DATA(ExpressionTraitExpr, { addData(S->getTrait()); })
341 DEF_ADD_DATA(PredefinedExpr, { addData(S->getIdentType()); })
342 DEF_ADD_DATA(TypeTraitExpr, {
343 addData(S->getTrait());
344 for (unsigned i = 0; i < S->getNumArgs(); ++i)
345 addData(S->getArg(i)->getType());
348 //--- Calls --------------------------------------------------------------//
349 DEF_ADD_DATA(CallExpr, {
350 // Function pointers don't have a callee and we just skip hashing it.
351 if (const FunctionDecl *D = S->getDirectCallee()) {
352 // If the function is a template specialization, we also need to handle
353 // the template arguments as they are not included in the qualified name.
354 if (auto Args = D->getTemplateSpecializationArgs()) {
355 std::string ArgString;
357 // Print all template arguments into ArgString
358 llvm::raw_string_ostream OS(ArgString);
359 for (unsigned i = 0; i < Args->size(); ++i) {
360 Args->get(i).print(Context.getLangOpts(), OS);
361 // Add a padding character so that 'foo<X, XX>()' != 'foo<XX, X>()'.
368 addData(D->getQualifiedNameAsString());
372 //--- Exceptions ---------------------------------------------------------//
373 DEF_ADD_DATA(CXXCatchStmt, { addData(S->getCaughtType()); })
375 //--- C++ OOP Stmts ------------------------------------------------------//
376 DEF_ADD_DATA(CXXDeleteExpr, {
377 addData(S->isArrayFormAsWritten());
378 addData(S->isGlobalDelete());
381 //--- Casts --------------------------------------------------------------//
382 DEF_ADD_DATA(ObjCBridgedCastExpr, { addData(S->getBridgeKind()); })
384 //--- Miscellaneous Exprs ------------------------------------------------//
385 DEF_ADD_DATA(BinaryOperator, { addData(S->getOpcode()); })
386 DEF_ADD_DATA(UnaryOperator, { addData(S->getOpcode()); })
388 //--- Control flow -------------------------------------------------------//
389 DEF_ADD_DATA(GotoStmt, { addData(S->getLabel()->getName()); })
390 DEF_ADD_DATA(IndirectGotoStmt, {
391 if (S->getConstantTarget())
392 addData(S->getConstantTarget()->getName());
394 DEF_ADD_DATA(LabelStmt, { addData(S->getDecl()->getName()); })
395 DEF_ADD_DATA(MSDependentExistsStmt, { addData(S->isIfExists()); })
396 DEF_ADD_DATA(AddrLabelExpr, { addData(S->getLabel()->getName()); })
398 //--- Objective-C --------------------------------------------------------//
399 DEF_ADD_DATA(ObjCIndirectCopyRestoreExpr, { addData(S->shouldCopy()); })
400 DEF_ADD_DATA(ObjCPropertyRefExpr, {
401 addData(S->isSuperReceiver());
402 addData(S->isImplicitProperty());
404 DEF_ADD_DATA(ObjCAtCatchStmt, { addData(S->hasEllipsis()); })
406 //--- Miscellaneous Stmts ------------------------------------------------//
407 DEF_ADD_DATA(CXXFoldExpr, {
408 addData(S->isRightFold());
409 addData(S->getOperator());
411 DEF_ADD_DATA(GenericSelectionExpr, {
412 for (unsigned i = 0; i < S->getNumAssocs(); ++i) {
413 addData(S->getAssocType(i));
416 DEF_ADD_DATA(LambdaExpr, {
417 for (const LambdaCapture &C : S->captures()) {
418 addData(C.isPackExpansion());
419 addData(C.getCaptureKind());
420 if (C.capturesVariable())
421 addData(C.getCapturedVar()->getType());
423 addData(S->isGenericLambda());
424 addData(S->isMutable());
426 DEF_ADD_DATA(DeclStmt, {
427 auto numDecls = std::distance(S->decl_begin(), S->decl_end());
428 addData(static_cast<CloneDetector::DataPiece>(numDecls));
429 for (const Decl *D : S->decls()) {
430 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
431 addData(VD->getType());
435 DEF_ADD_DATA(AsmStmt, {
436 addData(S->isSimple());
437 addData(S->isVolatile());
438 addData(S->generateAsmString(Context));
439 for (unsigned i = 0; i < S->getNumInputs(); ++i) {
440 addData(S->getInputConstraint(i));
442 for (unsigned i = 0; i < S->getNumOutputs(); ++i) {
443 addData(S->getOutputConstraint(i));
445 for (unsigned i = 0; i < S->getNumClobbers(); ++i) {
446 addData(S->getClobber(i));
449 DEF_ADD_DATA(AttributedStmt, {
450 for (const Attr *A : S->getAttrs()) {
451 addData(std::string(A->getSpelling()));
455 } // end anonymous namespace
458 /// Generates CloneSignatures for a set of statements and stores the results in
459 /// a CloneDetector object.
460 class CloneSignatureGenerator {
465 /// \brief Generates CloneSignatures for all statements in the given statement
466 /// tree and stores them in the CloneDetector.
468 /// \param S The root of the given statement tree.
469 /// \param ParentMacroStack A string representing the macros that generated
470 /// the parent statement or an empty string if no
471 /// macros generated the parent statement.
472 /// See getMacroStack() for generating such a string.
473 /// \return The CloneSignature of the root statement.
474 CloneDetector::CloneSignature
475 generateSignatures(const Stmt *S, const std::string &ParentMacroStack) {
476 // Create an empty signature that will be filled in this method.
477 CloneDetector::CloneSignature Signature;
481 // Collect all relevant data from S and hash it.
482 StmtDataCollector<llvm::MD5>(S, Context, Hash);
484 // Look up what macros expanded into the current statement.
485 std::string StartMacroStack = getMacroStack(S->getLocStart(), Context);
486 std::string EndMacroStack = getMacroStack(S->getLocEnd(), Context);
488 // First, check if ParentMacroStack is not empty which means we are currently
489 // dealing with a parent statement which was expanded from a macro.
490 // If this parent statement was expanded from the same macros as this
491 // statement, we reduce the initial complexity of this statement to zero.
492 // This causes that a group of statements that were generated by a single
493 // macro expansion will only increase the total complexity by one.
494 // Note: This is not the final complexity of this statement as we still
495 // add the complexity of the child statements to the complexity value.
496 if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack &&
497 EndMacroStack == ParentMacroStack)) {
498 Signature.Complexity = 0;
501 // Storage for the signatures of the direct child statements. This is only
502 // needed if the current statement is a CompoundStmt.
503 std::vector<CloneDetector::CloneSignature> ChildSignatures;
504 const CompoundStmt *CS = dyn_cast<const CompoundStmt>(S);
506 // The signature of a statement includes the signatures of its children.
507 // Therefore we create the signatures for every child and add them to the
508 // current signature.
509 for (const Stmt *Child : S->children()) {
510 // Some statements like 'if' can have nullptr children that we will skip.
514 // Recursive call to create the signature of the child statement. This
515 // will also create and store all clone groups in this child statement.
516 // We pass only the StartMacroStack along to keep things simple.
517 auto ChildSignature = generateSignatures(Child, StartMacroStack);
519 // Add the collected data to the signature of the current statement.
520 Signature.Complexity += ChildSignature.Complexity;
521 Hash.update(StringRef(reinterpret_cast<char *>(&ChildSignature.Hash),
522 sizeof(ChildSignature.Hash)));
524 // If the current statement is a CompoundStatement, we need to store the
525 // signature for the generation of the sub-sequences.
527 ChildSignatures.push_back(ChildSignature);
530 // If the current statement is a CompoundStmt, we also need to create the
531 // clone groups from the sub-sequences inside the children.
533 handleSubSequences(CS, ChildSignatures);
535 // Create the final hash code for the current signature.
536 llvm::MD5::MD5Result HashResult;
537 Hash.final(HashResult);
539 // Copy as much of the generated hash code to the signature's hash code.
540 std::memcpy(&Signature.Hash, &HashResult,
541 std::min(sizeof(Signature.Hash), sizeof(HashResult)));
543 // Save the signature for the current statement in the CloneDetector object.
544 CD.add(StmtSequence(S, Context), Signature);
549 /// \brief Adds all possible sub-sequences in the child array of the given
550 /// CompoundStmt to the CloneDetector.
551 /// \param CS The given CompoundStmt.
552 /// \param ChildSignatures A list of calculated signatures for each child in
553 /// the given CompoundStmt.
554 void handleSubSequences(
555 const CompoundStmt *CS,
556 const std::vector<CloneDetector::CloneSignature> &ChildSignatures) {
558 // FIXME: This function has quadratic runtime right now. Check if skipping
559 // this function for too long CompoundStmts is an option.
561 // The length of the sub-sequence. We don't need to handle sequences with
562 // the length 1 as they are already handled in CollectData().
563 for (unsigned Length = 2; Length <= CS->size(); ++Length) {
564 // The start index in the body of the CompoundStmt. We increase the
565 // position until the end of the sub-sequence reaches the end of the
566 // CompoundStmt body.
567 for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
568 // Create an empty signature and add the signatures of all selected
569 // child statements to it.
570 CloneDetector::CloneSignature SubSignature;
573 for (unsigned i = Pos; i < Pos + Length; ++i) {
574 SubSignature.Complexity += ChildSignatures[i].Complexity;
575 size_t ChildHash = ChildSignatures[i].Hash;
577 SubHash.update(StringRef(reinterpret_cast<char *>(&ChildHash),
581 // Create the final hash code for the current signature.
582 llvm::MD5::MD5Result HashResult;
583 SubHash.final(HashResult);
585 // Copy as much of the generated hash code to the signature's hash code.
586 std::memcpy(&SubSignature.Hash, &HashResult,
587 std::min(sizeof(SubSignature.Hash), sizeof(HashResult)));
589 // Save the signature together with the information about what children
590 // sequence we selected.
591 CD.add(StmtSequence(CS, Context, Pos, Pos + Length), SubSignature);
597 explicit CloneSignatureGenerator(CloneDetector &CD, ASTContext &Context)
598 : CD(CD), Context(Context) {}
600 /// \brief Generates signatures for all statements in the given function body.
601 void consumeCodeBody(const Stmt *S) { generateSignatures(S, ""); }
603 } // end anonymous namespace
605 void CloneDetector::analyzeCodeBody(const Decl *D) {
607 assert(D->hasBody());
608 CloneSignatureGenerator Generator(*this, D->getASTContext());
609 Generator.consumeCodeBody(D->getBody());
612 void CloneDetector::add(const StmtSequence &S,
613 const CloneSignature &Signature) {
614 Sequences.push_back(std::make_pair(Signature, S));
618 /// \brief Returns true if and only if \p Stmt contains at least one other
619 /// sequence in the \p Group.
620 bool containsAnyInGroup(StmtSequence &Stmt, CloneDetector::CloneGroup &Group) {
621 for (StmtSequence &GroupStmt : Group.Sequences) {
622 if (Stmt.contains(GroupStmt))
628 /// \brief Returns true if and only if all sequences in \p OtherGroup are
629 /// contained by a sequence in \p Group.
630 bool containsGroup(CloneDetector::CloneGroup &Group,
631 CloneDetector::CloneGroup &OtherGroup) {
632 // We have less sequences in the current group than we have in the other,
633 // so we will never fulfill the requirement for returning true. This is only
634 // possible because we know that a sequence in Group can contain at most
635 // one sequence in OtherGroup.
636 if (Group.Sequences.size() < OtherGroup.Sequences.size())
639 for (StmtSequence &Stmt : Group.Sequences) {
640 if (!containsAnyInGroup(Stmt, OtherGroup))
645 } // end anonymous namespace
648 /// \brief Wrapper around FoldingSetNodeID that it can be used as the template
649 /// argument of the StmtDataCollector.
650 class FoldingSetNodeIDWrapper {
652 llvm::FoldingSetNodeID &FS;
655 FoldingSetNodeIDWrapper(llvm::FoldingSetNodeID &FS) : FS(FS) {}
657 void update(StringRef Str) { FS.AddString(Str); }
659 } // end anonymous namespace
661 /// \brief Writes the relevant data from all statements and child statements
662 /// in the given StmtSequence into the given FoldingSetNodeID.
663 static void CollectStmtSequenceData(const StmtSequence &Sequence,
664 FoldingSetNodeIDWrapper &OutputData) {
665 for (const Stmt *S : Sequence) {
666 StmtDataCollector<FoldingSetNodeIDWrapper>(S, Sequence.getASTContext(),
669 for (const Stmt *Child : S->children()) {
673 CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()),
679 /// \brief Returns true if both sequences are clones of each other.
680 static bool areSequencesClones(const StmtSequence &LHS,
681 const StmtSequence &RHS) {
682 // We collect the data from all statements in the sequence as we did before
683 // when generating a hash value for each sequence. But this time we don't
684 // hash the collected data and compare the whole data set instead. This
685 // prevents any false-positives due to hash code collisions.
686 llvm::FoldingSetNodeID DataLHS, DataRHS;
687 FoldingSetNodeIDWrapper LHSWrapper(DataLHS);
688 FoldingSetNodeIDWrapper RHSWrapper(DataRHS);
690 CollectStmtSequenceData(LHS, LHSWrapper);
691 CollectStmtSequenceData(RHS, RHSWrapper);
693 return DataLHS == DataRHS;
696 /// \brief Finds all actual clone groups in a single group of presumed clones.
697 /// \param Result Output parameter to which all found groups are added.
698 /// \param Group A group of presumed clones. The clones are allowed to have a
699 /// different variable pattern and may not be actual clones of each
701 /// \param CheckVariablePattern If true, every clone in a group that was added
702 /// to the output follows the same variable pattern as the other
703 /// clones in its group.
704 static void createCloneGroups(std::vector<CloneDetector::CloneGroup> &Result,
705 const CloneDetector::CloneGroup &Group,
706 bool CheckVariablePattern) {
707 // We remove the Sequences one by one, so a list is more appropriate.
708 std::list<StmtSequence> UnassignedSequences(Group.Sequences.begin(),
709 Group.Sequences.end());
711 // Search for clones as long as there could be clones in UnassignedSequences.
712 while (UnassignedSequences.size() > 1) {
714 // Pick the first Sequence as a protoype for a new clone group.
715 StmtSequence Prototype = UnassignedSequences.front();
716 UnassignedSequences.pop_front();
718 CloneDetector::CloneGroup FilteredGroup(Prototype, Group.Signature);
720 // Analyze the variable pattern of the prototype. Every other StmtSequence
721 // needs to have the same pattern to get into the new clone group.
722 VariablePattern PrototypeFeatures(Prototype);
724 // Search all remaining StmtSequences for an identical variable pattern
725 // and assign them to our new clone group.
726 auto I = UnassignedSequences.begin(), E = UnassignedSequences.end();
728 // If the sequence doesn't fit to the prototype, we have encountered
729 // an unintended hash code collision and we skip it.
730 if (!areSequencesClones(Prototype, *I)) {
735 // If we weren't asked to check for a matching variable pattern in clone
736 // groups we can add the sequence now to the new clone group.
737 // If we were asked to check for matching variable pattern, we first have
738 // to check that there are no differences between the two patterns and
739 // only proceed if they match.
740 if (!CheckVariablePattern ||
741 VariablePattern(*I).countPatternDifferences(PrototypeFeatures) == 0) {
742 FilteredGroup.Sequences.push_back(*I);
743 I = UnassignedSequences.erase(I);
747 // We didn't found a matching variable pattern, so we continue with the
752 // Add a valid clone group to the list of found clone groups.
753 if (!FilteredGroup.isValid())
756 Result.push_back(FilteredGroup);
760 void CloneDetector::findClones(std::vector<CloneGroup> &Result,
761 unsigned MinGroupComplexity,
762 bool CheckPatterns) {
763 // A shortcut (and necessary for the for-loop later in this function).
764 if (Sequences.empty())
767 // We need to search for groups of StmtSequences with the same hash code to
768 // create our initial clone groups. By sorting all known StmtSequences by
769 // their hash value we make sure that StmtSequences with the same hash code
770 // are grouped together in the Sequences vector.
771 // Note: We stable sort here because the StmtSequences are added in the order
772 // in which they appear in the source file. We want to preserve that order
773 // because we also want to report them in that order in the CloneChecker.
774 std::stable_sort(Sequences.begin(), Sequences.end(),
775 [](std::pair<CloneSignature, StmtSequence> LHS,
776 std::pair<CloneSignature, StmtSequence> RHS) {
777 return LHS.first.Hash < RHS.first.Hash;
780 std::vector<CloneGroup> CloneGroups;
782 // Check for each CloneSignature if its successor has the same hash value.
783 // We don't check the last CloneSignature as it has no successor.
784 // Note: The 'size - 1' in the condition is safe because we check for an empty
785 // Sequences vector at the beginning of this function.
786 for (unsigned i = 0; i < Sequences.size() - 1; ++i) {
787 const auto Current = Sequences[i];
788 const auto Next = Sequences[i + 1];
790 if (Current.first.Hash != Next.first.Hash)
793 // It's likely that we just found an sequence of CloneSignatures that
794 // represent a CloneGroup, so we create a new group and start checking and
795 // adding the CloneSignatures in this sequence.
797 Group.Signature = Current.first;
799 for (; i < Sequences.size(); ++i) {
800 const auto &Signature = Sequences[i];
802 // A different hash value means we have reached the end of the sequence.
803 if (Current.first.Hash != Signature.first.Hash) {
804 // The current Signature could be the start of a new CloneGroup. So we
805 // decrement i so that we visit it again in the outer loop.
806 // Note: i can never be 0 at this point because we are just comparing
807 // the hash of the Current CloneSignature with itself in the 'if' above.
813 // Skip CloneSignatures that won't pass the complexity requirement.
814 if (Signature.first.Complexity < MinGroupComplexity)
817 Group.Sequences.push_back(Signature.second);
820 // There is a chance that we haven't found more than two fitting
821 // CloneSignature because not enough CloneSignatures passed the complexity
822 // requirement. As a CloneGroup with less than two members makes no sense,
823 // we ignore this CloneGroup and won't add it to the result.
824 if (!Group.isValid())
827 CloneGroups.push_back(Group);
830 // Add every valid clone group that fulfills the complexity requirement.
831 for (const CloneGroup &Group : CloneGroups) {
832 createCloneGroups(Result, Group, CheckPatterns);
835 std::vector<unsigned> IndexesToRemove;
837 // Compare every group in the result with the rest. If one groups contains
838 // another group, we only need to return the bigger group.
839 // Note: This doesn't scale well, so if possible avoid calling any heavy
840 // function from this loop to minimize the performance impact.
841 for (unsigned i = 0; i < Result.size(); ++i) {
842 for (unsigned j = 0; j < Result.size(); ++j) {
843 // Don't compare a group with itself.
847 if (containsGroup(Result[j], Result[i])) {
848 IndexesToRemove.push_back(i);
854 // Erasing a list of indexes from the vector should be done with decreasing
855 // indexes. As IndexesToRemove is constructed with increasing values, we just
856 // reverse iterate over it to get the desired order.
857 for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); ++I) {
858 Result.erase(Result.begin() + *I);
862 void CloneDetector::findSuspiciousClones(
863 std::vector<CloneDetector::SuspiciousClonePair> &Result,
864 unsigned MinGroupComplexity) {
865 std::vector<CloneGroup> Clones;
866 // Reuse the normal search for clones but specify that the clone groups don't
867 // need to have a common referenced variable pattern so that we can manually
868 // search for the kind of pattern errors this function is supposed to find.
869 findClones(Clones, MinGroupComplexity, false);
871 for (const CloneGroup &Group : Clones) {
872 for (unsigned i = 0; i < Group.Sequences.size(); ++i) {
873 VariablePattern PatternA(Group.Sequences[i]);
875 for (unsigned j = i + 1; j < Group.Sequences.size(); ++j) {
876 VariablePattern PatternB(Group.Sequences[j]);
878 CloneDetector::SuspiciousClonePair ClonePair;
879 // For now, we only report clones which break the variable pattern just
880 // once because multiple differences in a pattern are an indicator that
881 // those differences are maybe intended (e.g. because it's actually
882 // a different algorithm).
883 // TODO: In very big clones even multiple variables can be unintended,
884 // so replacing this number with a percentage could better handle such
885 // cases. On the other hand it could increase the false-positive rate
886 // for all clones if the percentage is too high.
887 if (PatternA.countPatternDifferences(PatternB, &ClonePair) == 1) {
888 Result.push_back(ClonePair);