624 lines · cpp
1//===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8///9/// This file implements classes for searching and analyzing source code clones.10///11//===----------------------------------------------------------------------===//12 13#include "clang/Analysis/CloneDetection.h"14#include "clang/AST/Attr.h"15#include "clang/AST/DataCollection.h"16#include "clang/Basic/SourceManager.h"17#include "llvm/Support/MD5.h"18#include "llvm/Support/Path.h"19 20using namespace clang;21 22StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D,23 unsigned StartIndex, unsigned EndIndex)24 : S(Stmt), D(D), StartIndex(StartIndex), EndIndex(EndIndex) {25 assert(Stmt && "Stmt must not be a nullptr");26 assert(StartIndex < EndIndex && "Given array should not be empty");27 assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt");28}29 30StmtSequence::StmtSequence(const Stmt *Stmt, const Decl *D)31 : S(Stmt), D(D), StartIndex(0), EndIndex(0) {}32 33StmtSequence::StmtSequence()34 : S(nullptr), D(nullptr), StartIndex(0), EndIndex(0) {}35 36bool StmtSequence::contains(const StmtSequence &Other) const {37 // If both sequences reside in different declarations, they can never contain38 // each other.39 if (D != Other.D)40 return false;41 42 const SourceManager &SM = getASTContext().getSourceManager();43 44 // Otherwise check if the start and end locations of the current sequence45 // surround the other sequence.46 bool StartIsInBounds =47 SM.isBeforeInTranslationUnit(getBeginLoc(), Other.getBeginLoc()) ||48 getBeginLoc() == Other.getBeginLoc();49 if (!StartIsInBounds)50 return false;51 52 bool EndIsInBounds =53 SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) ||54 Other.getEndLoc() == getEndLoc();55 return EndIsInBounds;56}57 58StmtSequence::iterator StmtSequence::begin() const {59 if (!holdsSequence()) {60 return &S;61 }62 auto CS = cast<CompoundStmt>(S);63 return CS->body_begin() + StartIndex;64}65 66StmtSequence::iterator StmtSequence::end() const {67 if (!holdsSequence()) {68 return reinterpret_cast<StmtSequence::iterator>(&S) + 1;69 }70 auto CS = cast<CompoundStmt>(S);71 return CS->body_begin() + EndIndex;72}73 74ASTContext &StmtSequence::getASTContext() const {75 assert(D);76 return D->getASTContext();77}78 79SourceLocation StmtSequence::getBeginLoc() const {80 return front()->getBeginLoc();81}82 83SourceLocation StmtSequence::getEndLoc() const { return back()->getEndLoc(); }84 85SourceRange StmtSequence::getSourceRange() const {86 return SourceRange(getBeginLoc(), getEndLoc());87}88 89void CloneDetector::analyzeCodeBody(const Decl *D) {90 assert(D);91 assert(D->hasBody());92 93 Sequences.push_back(StmtSequence(D->getBody(), D));94}95 96/// Returns true if and only if \p Stmt contains at least one other97/// sequence in the \p Group.98static bool containsAnyInGroup(StmtSequence &Seq,99 CloneDetector::CloneGroup &Group) {100 for (StmtSequence &GroupSeq : Group) {101 if (Seq.contains(GroupSeq))102 return true;103 }104 return false;105}106 107/// Returns true if and only if all sequences in \p OtherGroup are108/// contained by a sequence in \p Group.109static bool containsGroup(CloneDetector::CloneGroup &Group,110 CloneDetector::CloneGroup &OtherGroup) {111 // We have less sequences in the current group than we have in the other,112 // so we will never fulfill the requirement for returning true. This is only113 // possible because we know that a sequence in Group can contain at most114 // one sequence in OtherGroup.115 if (Group.size() < OtherGroup.size())116 return false;117 118 for (StmtSequence &Stmt : Group) {119 if (!containsAnyInGroup(Stmt, OtherGroup))120 return false;121 }122 return true;123}124 125void OnlyLargestCloneConstraint::constrain(126 std::vector<CloneDetector::CloneGroup> &Result) {127 std::vector<unsigned> IndexesToRemove;128 129 // Compare every group in the result with the rest. If one groups contains130 // another group, we only need to return the bigger group.131 // Note: This doesn't scale well, so if possible avoid calling any heavy132 // function from this loop to minimize the performance impact.133 for (unsigned i = 0; i < Result.size(); ++i) {134 for (unsigned j = 0; j < Result.size(); ++j) {135 // Don't compare a group with itself.136 if (i == j)137 continue;138 139 if (containsGroup(Result[j], Result[i])) {140 IndexesToRemove.push_back(i);141 break;142 }143 }144 }145 146 // Erasing a list of indexes from the vector should be done with decreasing147 // indexes. As IndexesToRemove is constructed with increasing values, we just148 // reverse iterate over it to get the desired order.149 for (unsigned I : llvm::reverse(IndexesToRemove))150 Result.erase(Result.begin() + I);151}152 153bool FilenamePatternConstraint::isAutoGenerated(154 const CloneDetector::CloneGroup &Group) {155 if (IgnoredFilesPattern.empty() || Group.empty() ||156 !IgnoredFilesRegex->isValid())157 return false;158 159 for (const StmtSequence &S : Group) {160 const SourceManager &SM = S.getASTContext().getSourceManager();161 StringRef Filename = llvm::sys::path::filename(162 SM.getFilename(S.getContainingDecl()->getLocation()));163 if (IgnoredFilesRegex->match(Filename))164 return true;165 }166 167 return false;168}169 170/// This class defines what a type II code clone is: If it collects for two171/// statements the same data, then those two statements are considered to be172/// clones of each other.173///174/// All collected data is forwarded to the given data consumer of the type T.175/// The data consumer class needs to provide a member method with the signature:176/// update(StringRef Str)177namespace {178template <class T>179class CloneTypeIIStmtDataCollector180 : public ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>> {181 ASTContext &Context;182 /// The data sink to which all data is forwarded.183 T &DataConsumer;184 185 template <class Ty> void addData(const Ty &Data) {186 data_collection::addDataToConsumer(DataConsumer, Data);187 }188 189public:190 CloneTypeIIStmtDataCollector(const Stmt *S, ASTContext &Context,191 T &DataConsumer)192 : Context(Context), DataConsumer(DataConsumer) {193 this->Visit(S);194 }195 196// Define a visit method for each class to collect data and subsequently visit197// all parent classes. This uses a template so that custom visit methods by us198// take precedence.199#define DEF_ADD_DATA(CLASS, CODE) \200 template <class = void> void Visit##CLASS(const CLASS *S) { \201 CODE; \202 ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \203 }204 205#include "clang/AST/StmtDataCollectors.inc"206 207// Type II clones ignore variable names and literals, so let's skip them.208#define SKIP(CLASS) \209 void Visit##CLASS(const CLASS *S) { \210 ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \211 }212 SKIP(DeclRefExpr)213 SKIP(MemberExpr)214 SKIP(IntegerLiteral)215 SKIP(FloatingLiteral)216 SKIP(StringLiteral)217 SKIP(CXXBoolLiteralExpr)218 SKIP(CharacterLiteral)219#undef SKIP220};221} // end anonymous namespace222 223static size_t createHash(llvm::MD5 &Hash) {224 size_t HashCode;225 226 // Create the final hash code for the current Stmt.227 llvm::MD5::MD5Result HashResult;228 Hash.final(HashResult);229 230 // Copy as much as possible of the generated hash code to the Stmt's hash231 // code.232 std::memcpy(&HashCode, &HashResult,233 std::min(sizeof(HashCode), sizeof(HashResult)));234 235 return HashCode;236}237 238/// Generates and saves a hash code for the given Stmt.239/// \param S The given Stmt.240/// \param D The Decl containing S.241/// \param StmtsByHash Output parameter that will contain the hash codes for242/// each StmtSequence in the given Stmt.243/// \return The hash code of the given Stmt.244///245/// If the given Stmt is a CompoundStmt, this method will also generate246/// hashes for all possible StmtSequences in the children of this Stmt.247static size_t248saveHash(const Stmt *S, const Decl *D,249 std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) {250 llvm::MD5 Hash;251 ASTContext &Context = D->getASTContext();252 253 CloneTypeIIStmtDataCollector<llvm::MD5>(S, Context, Hash);254 255 auto CS = dyn_cast<CompoundStmt>(S);256 SmallVector<size_t, 8> ChildHashes;257 258 for (const Stmt *Child : S->children()) {259 if (Child == nullptr) {260 ChildHashes.push_back(0);261 continue;262 }263 size_t ChildHash = saveHash(Child, D, StmtsByHash);264 Hash.update(265 StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));266 ChildHashes.push_back(ChildHash);267 }268 269 if (CS) {270 // If we're in a CompoundStmt, we hash all possible combinations of child271 // statements to find clones in those subsequences.272 // We first go through every possible starting position of a subsequence.273 for (unsigned Pos = 0; Pos < CS->size(); ++Pos) {274 // Then we try all possible lengths this subsequence could have and275 // reuse the same hash object to make sure we only hash every child276 // hash exactly once.277 llvm::MD5 Hash;278 for (unsigned Length = 1; Length <= CS->size() - Pos; ++Length) {279 // Grab the current child hash and put it into our hash. We do280 // -1 on the index because we start counting the length at 1.281 size_t ChildHash = ChildHashes[Pos + Length - 1];282 Hash.update(283 StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));284 // If we have at least two elements in our subsequence, we can start285 // saving it.286 if (Length > 1) {287 llvm::MD5 SubHash = Hash;288 StmtsByHash.push_back(std::make_pair(289 createHash(SubHash), StmtSequence(CS, D, Pos, Pos + Length)));290 }291 }292 }293 }294 295 size_t HashCode = createHash(Hash);296 StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D)));297 return HashCode;298}299 300namespace {301/// Wrapper around FoldingSetNodeID that it can be used as the template302/// argument of the StmtDataCollector.303class FoldingSetNodeIDWrapper {304 305 llvm::FoldingSetNodeID &FS;306 307public:308 FoldingSetNodeIDWrapper(llvm::FoldingSetNodeID &FS) : FS(FS) {}309 310 void update(StringRef Str) { FS.AddString(Str); }311};312} // end anonymous namespace313 314/// Writes the relevant data from all statements and child statements315/// in the given StmtSequence into the given FoldingSetNodeID.316static void CollectStmtSequenceData(const StmtSequence &Sequence,317 FoldingSetNodeIDWrapper &OutputData) {318 for (const Stmt *S : Sequence) {319 CloneTypeIIStmtDataCollector<FoldingSetNodeIDWrapper>(320 S, Sequence.getASTContext(), OutputData);321 322 for (const Stmt *Child : S->children()) {323 if (!Child)324 continue;325 326 CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()),327 OutputData);328 }329 }330}331 332/// Returns true if both sequences are clones of each other.333static bool areSequencesClones(const StmtSequence &LHS,334 const StmtSequence &RHS) {335 // We collect the data from all statements in the sequence as we did before336 // when generating a hash value for each sequence. But this time we don't337 // hash the collected data and compare the whole data set instead. This338 // prevents any false-positives due to hash code collisions.339 llvm::FoldingSetNodeID DataLHS, DataRHS;340 FoldingSetNodeIDWrapper LHSWrapper(DataLHS);341 FoldingSetNodeIDWrapper RHSWrapper(DataRHS);342 343 CollectStmtSequenceData(LHS, LHSWrapper);344 CollectStmtSequenceData(RHS, RHSWrapper);345 346 return DataLHS == DataRHS;347}348 349void RecursiveCloneTypeIIHashConstraint::constrain(350 std::vector<CloneDetector::CloneGroup> &Sequences) {351 // FIXME: Maybe we can do this in-place and don't need this additional vector.352 std::vector<CloneDetector::CloneGroup> Result;353 354 for (CloneDetector::CloneGroup &Group : Sequences) {355 // We assume in the following code that the Group is non-empty, so we356 // skip all empty groups.357 if (Group.empty())358 continue;359 360 std::vector<std::pair<size_t, StmtSequence>> StmtsByHash;361 362 // Generate hash codes for all children of S and save them in StmtsByHash.363 for (const StmtSequence &S : Group) {364 saveHash(S.front(), S.getContainingDecl(), StmtsByHash);365 }366 367 // Sort hash_codes in StmtsByHash.368 llvm::stable_sort(StmtsByHash, llvm::less_first());369 370 // Check for each StmtSequence if its successor has the same hash value.371 // We don't check the last StmtSequence as it has no successor.372 // Note: The 'size - 1 ' in the condition is safe because we check for an373 // empty Group vector at the beginning of this function.374 for (unsigned i = 0; i < StmtsByHash.size() - 1; ++i) {375 const auto Current = StmtsByHash[i];376 377 // It's likely that we just found a sequence of StmtSequences that378 // represent a CloneGroup, so we create a new group and start checking and379 // adding the StmtSequences in this sequence.380 CloneDetector::CloneGroup NewGroup;381 382 size_t PrototypeHash = Current.first;383 384 for (; i < StmtsByHash.size(); ++i) {385 // A different hash value means we have reached the end of the sequence.386 if (PrototypeHash != StmtsByHash[i].first) {387 // The current sequence could be the start of a new CloneGroup. So we388 // decrement i so that we visit it again in the outer loop.389 // Note: i can never be 0 at this point because we are just comparing390 // the hash of the Current StmtSequence with itself in the 'if' above.391 assert(i != 0);392 --i;393 break;394 }395 // Same hash value means we should add the StmtSequence to the current396 // group.397 NewGroup.push_back(StmtsByHash[i].second);398 }399 400 // We created a new clone group with matching hash codes and move it to401 // the result vector.402 Result.push_back(NewGroup);403 }404 }405 // Sequences is the output parameter, so we copy our result into it.406 Sequences = Result;407}408 409void RecursiveCloneTypeIIVerifyConstraint::constrain(410 std::vector<CloneDetector::CloneGroup> &Sequences) {411 CloneConstraint::splitCloneGroups(412 Sequences, [](const StmtSequence &A, const StmtSequence &B) {413 return areSequencesClones(A, B);414 });415}416 417size_t MinComplexityConstraint::calculateStmtComplexity(418 const StmtSequence &Seq, std::size_t Limit,419 const std::string &ParentMacroStack) {420 if (Seq.empty())421 return 0;422 423 size_t Complexity = 1;424 425 ASTContext &Context = Seq.getASTContext();426 427 // Look up what macros expanded into the current statement.428 std::string MacroStack =429 data_collection::getMacroStack(Seq.getBeginLoc(), Context);430 431 // First, check if ParentMacroStack is not empty which means we are currently432 // dealing with a parent statement which was expanded from a macro.433 // If this parent statement was expanded from the same macros as this434 // statement, we reduce the initial complexity of this statement to zero.435 // This causes that a group of statements that were generated by a single436 // macro expansion will only increase the total complexity by one.437 // Note: This is not the final complexity of this statement as we still438 // add the complexity of the child statements to the complexity value.439 if (!ParentMacroStack.empty() && MacroStack == ParentMacroStack) {440 Complexity = 0;441 }442 443 // Iterate over the Stmts in the StmtSequence and add their complexity values444 // to the current complexity value.445 if (Seq.holdsSequence()) {446 for (const Stmt *S : Seq) {447 Complexity += calculateStmtComplexity(448 StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack);449 if (Complexity >= Limit)450 return Limit;451 }452 } else {453 for (const Stmt *S : Seq.front()->children()) {454 Complexity += calculateStmtComplexity(455 StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack);456 if (Complexity >= Limit)457 return Limit;458 }459 }460 return Complexity;461}462 463void MatchingVariablePatternConstraint::constrain(464 std::vector<CloneDetector::CloneGroup> &CloneGroups) {465 CloneConstraint::splitCloneGroups(466 CloneGroups, [](const StmtSequence &A, const StmtSequence &B) {467 VariablePattern PatternA(A);468 VariablePattern PatternB(B);469 return PatternA.countPatternDifferences(PatternB) == 0;470 });471}472 473void CloneConstraint::splitCloneGroups(474 std::vector<CloneDetector::CloneGroup> &CloneGroups,475 llvm::function_ref<bool(const StmtSequence &, const StmtSequence &)>476 Compare) {477 std::vector<CloneDetector::CloneGroup> Result;478 for (auto &HashGroup : CloneGroups) {479 // Contains all indexes in HashGroup that were already added to a480 // CloneGroup.481 std::vector<char> Indexes;482 Indexes.resize(HashGroup.size());483 484 for (unsigned i = 0; i < HashGroup.size(); ++i) {485 // Skip indexes that are already part of a CloneGroup.486 if (Indexes[i])487 continue;488 489 // Pick the first unhandled StmtSequence and consider it as the490 // beginning491 // of a new CloneGroup for now.492 // We don't add i to Indexes because we never iterate back.493 StmtSequence Prototype = HashGroup[i];494 CloneDetector::CloneGroup PotentialGroup = {Prototype};495 ++Indexes[i];496 497 // Check all following StmtSequences for clones.498 for (unsigned j = i + 1; j < HashGroup.size(); ++j) {499 // Skip indexes that are already part of a CloneGroup.500 if (Indexes[j])501 continue;502 503 // If a following StmtSequence belongs to our CloneGroup, we add it.504 const StmtSequence &Candidate = HashGroup[j];505 506 if (!Compare(Prototype, Candidate))507 continue;508 509 PotentialGroup.push_back(Candidate);510 // Make sure we never visit this StmtSequence again.511 ++Indexes[j];512 }513 514 // Otherwise, add it to the result and continue searching for more515 // groups.516 Result.push_back(PotentialGroup);517 }518 519 assert(llvm::all_of(Indexes, [](char c) { return c == 1; }));520 }521 CloneGroups = Result;522}523 524void VariablePattern::addVariableOccurence(const VarDecl *VarDecl,525 const Stmt *Mention) {526 // First check if we already reference this variable527 for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex) {528 if (Variables[KindIndex] == VarDecl) {529 // If yes, add a new occurrence that points to the existing entry in530 // the Variables vector.531 Occurences.emplace_back(KindIndex, Mention);532 return;533 }534 }535 // If this variable wasn't already referenced, add it to the list of536 // referenced variables and add a occurrence that points to this new entry.537 Occurences.emplace_back(Variables.size(), Mention);538 Variables.push_back(VarDecl);539}540 541void VariablePattern::addVariables(const Stmt *S) {542 // Sometimes we get a nullptr (such as from IfStmts which often have nullptr543 // children). We skip such statements as they don't reference any544 // variables.545 if (!S)546 return;547 548 // Check if S is a reference to a variable. If yes, add it to the pattern.549 if (auto D = dyn_cast<DeclRefExpr>(S)) {550 if (auto VD = dyn_cast<VarDecl>(D->getDecl()->getCanonicalDecl()))551 addVariableOccurence(VD, D);552 }553 554 // Recursively check all children of the given statement.555 for (const Stmt *Child : S->children()) {556 addVariables(Child);557 }558}559 560unsigned VariablePattern::countPatternDifferences(561 const VariablePattern &Other,562 VariablePattern::SuspiciousClonePair *FirstMismatch) {563 unsigned NumberOfDifferences = 0;564 565 assert(Other.Occurences.size() == Occurences.size());566 for (unsigned i = 0; i < Occurences.size(); ++i) {567 auto ThisOccurence = Occurences[i];568 auto OtherOccurence = Other.Occurences[i];569 if (ThisOccurence.KindID == OtherOccurence.KindID)570 continue;571 572 ++NumberOfDifferences;573 574 // If FirstMismatch is not a nullptr, we need to store information about575 // the first difference between the two patterns.576 if (FirstMismatch == nullptr)577 continue;578 579 // Only proceed if we just found the first difference as we only store580 // information about the first difference.581 if (NumberOfDifferences != 1)582 continue;583 584 const VarDecl *FirstSuggestion = nullptr;585 // If there is a variable available in the list of referenced variables586 // which wouldn't break the pattern if it is used in place of the587 // current variable, we provide this variable as the suggested fix.588 if (OtherOccurence.KindID < Variables.size())589 FirstSuggestion = Variables[OtherOccurence.KindID];590 591 // Store information about the first clone.592 FirstMismatch->FirstCloneInfo =593 VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo(594 Variables[ThisOccurence.KindID], ThisOccurence.Mention,595 FirstSuggestion);596 597 // Same as above but with the other clone. We do this for both clones as598 // we don't know which clone is the one containing the unintended599 // pattern error.600 const VarDecl *SecondSuggestion = nullptr;601 if (ThisOccurence.KindID < Other.Variables.size())602 SecondSuggestion = Other.Variables[ThisOccurence.KindID];603 604 // Store information about the second clone.605 FirstMismatch->SecondCloneInfo =606 VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo(607 Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention,608 SecondSuggestion);609 610 // SuspiciousClonePair guarantees that the first clone always has a611 // suggested variable associated with it. As we know that one of the two612 // clones in the pair always has suggestion, we swap the two clones613 // in case the first clone has no suggested variable which means that614 // the second clone has a suggested variable and should be first.615 if (!FirstMismatch->FirstCloneInfo.Suggestion)616 std::swap(FirstMismatch->FirstCloneInfo, FirstMismatch->SecondCloneInfo);617 618 // This ensures that we always have at least one suggestion in a pair.619 assert(FirstMismatch->FirstCloneInfo.Suggestion);620 }621 622 return NumberOfDifferences;623}624