diff options
| author | dim <dim@FreeBSD.org> | 2017-04-02 17:24:58 +0000 |
|---|---|---|
| committer | dim <dim@FreeBSD.org> | 2017-04-02 17:24:58 +0000 |
| commit | 60b571e49a90d38697b3aca23020d9da42fc7d7f (patch) | |
| tree | 99351324c24d6cb146b6285b6caffa4d26fce188 /contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp | |
| parent | bea1b22c7a9bce1dfdd73e6e5b65bc4752215180 (diff) | |
| download | FreeBSD-src-60b571e49a90d38697b3aca23020d9da42fc7d7f.zip FreeBSD-src-60b571e49a90d38697b3aca23020d9da42fc7d7f.tar.gz | |
Update clang, llvm, lld, lldb, compiler-rt and libc++ to 4.0.0 release:
MFC r309142 (by emaste):
Add WITH_LLD_AS_LD build knob
If set it installs LLD as /usr/bin/ld. LLD (as of version 3.9) is not
capable of linking the world and kernel, but can self-host and link many
substantial applications. GNU ld continues to be used for the world and
kernel build, regardless of how this knob is set.
It is on by default for arm64, and off for all other CPU architectures.
Sponsored by: The FreeBSD Foundation
MFC r310840:
Reapply 310775, now it also builds correctly if lldb is disabled:
Move llvm-objdump from CLANG_EXTRAS to installed by default
We currently install three tools from binutils 2.17.50: as, ld, and
objdump. Work is underway to migrate to a permissively-licensed
tool-chain, with one goal being the retirement of binutils 2.17.50.
LLVM's llvm-objdump is intended to be compatible with GNU objdump
although it is currently missing some options and may have formatting
differences. Enable it by default for testing and further investigation.
It may later be changed to install as /usr/bin/objdump, it becomes a
fully viable replacement.
Reviewed by: emaste
Differential Revision: https://reviews.freebsd.org/D8879
MFC r312855 (by emaste):
Rename LLD_AS_LD to LLD_IS_LD, for consistency with CLANG_IS_CC
Reported by: Dan McGregor <dan.mcgregor usask.ca>
MFC r313559 | glebius | 2017-02-10 18:34:48 +0100 (Fri, 10 Feb 2017) | 5 lines
Don't check struct rtentry on FreeBSD, it is an internal kernel structure.
On other systems it may be API structure for SIOCADDRT/SIOCDELRT.
Reviewed by: emaste, dim
MFC r314152 (by jkim):
Remove an assembler flag, which is redundant since r309124. The upstream
took care of it by introducing a macro NO_EXEC_STACK_DIRECTIVE.
http://llvm.org/viewvc/llvm-project?rev=273500&view=rev
Reviewed by: dim
MFC r314564:
Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
4.0.0 (branches/release_40 296509). The release will follow soon.
Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
support to build; see UPDATING for more information.
Also note that as of 4.0.0, lld should be able to link the base system
on amd64 and aarch64. See the WITH_LLD_IS_LLD setting in src.conf(5).
Though please be aware that this is work in progress.
Release notes for llvm, clang and lld will be available here:
<http://releases.llvm.org/4.0.0/docs/ReleaseNotes.html>
<http://releases.llvm.org/4.0.0/tools/clang/docs/ReleaseNotes.html>
<http://releases.llvm.org/4.0.0/tools/lld/docs/ReleaseNotes.html>
Thanks to Ed Maste, Jan Beich, Antoine Brodin and Eric Fiselier for
their help.
Relnotes: yes
Exp-run: antoine
PR: 215969, 216008
MFC r314708:
For now, revert r287232 from upstream llvm trunk (by Daniil Fukalov):
[SCEV] limit recursion depth of CompareSCEVComplexity
Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled
loop) and runs almost infinite time.
Added cache of "equal" SCEV pairs to earlier cutoff of further
estimation. Recursion depth limit was also introduced as a parameter.
Reviewers: sanjoy
Subscribers: mzolotukhin, tstellarAMD, llvm-commits
Differential Revision: https://reviews.llvm.org/D26389
This commit is the cause of excessive compile times on skein_block.c
(and possibly other files) during kernel builds on amd64.
We never saw the problematic behavior described in this upstream commit,
so for now it is better to revert it. An upstream bug has been filed
here: https://bugs.llvm.org/show_bug.cgi?id=32142
Reported by: mjg
MFC r314795:
Reapply r287232 from upstream llvm trunk (by Daniil Fukalov):
[SCEV] limit recursion depth of CompareSCEVComplexity
Summary:
CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled
loop) and runs almost infinite time.
Added cache of "equal" SCEV pairs to earlier cutoff of further
estimation. Recursion depth limit was also introduced as a parameter.
Reviewers: sanjoy
Subscribers: mzolotukhin, tstellarAMD, llvm-commits
Differential Revision: https://reviews.llvm.org/D26389
Pull in r296992 from upstream llvm trunk (by Sanjoy Das):
[SCEV] Decrease the recursion threshold for CompareValueComplexity
Fixes PR32142.
r287232 accidentally increased the recursion threshold for
CompareValueComplexity from 2 to 32. This change reverses that
change by introducing a separate flag for CompareValueComplexity's
threshold.
The latter revision fixes the excessive compile times for skein_block.c.
MFC r314907 | mmel | 2017-03-08 12:40:27 +0100 (Wed, 08 Mar 2017) | 7 lines
Unbreak ARMv6 world.
The new compiler_rt library imported with clang 4.0.0 have several fatal
issues (non-functional __udivsi3 for example) with ARM specific instrict
functions. As temporary workaround, until upstream solve these problems,
disable all thumb[1][2] related feature.
MFC r315016:
Update clang, llvm, lld, lldb, compiler-rt and libc++ to 4.0.0 release.
We were already very close to the last release candidate, so this is a
pretty minor update.
Relnotes: yes
MFC r316005:
Revert r314907, and pull in r298713 from upstream compiler-rt trunk (by
Weiming Zhao):
builtins: Select correct code fragments when compiling for Thumb1/Thum2/ARM ISA.
Summary:
Value of __ARM_ARCH_ISA_THUMB isn't based on the actual compilation
mode (-mthumb, -marm), it reflect's capability of given CPU.
Due to this:
- use __tbumb__ and __thumb2__ insteand of __ARM_ARCH_ISA_THUMB
- use '.thumb' directive consistently in all affected files
- decorate all thumb functions using
DEFINE_COMPILERRT_THUMB_FUNCTION()
---------
Note: This patch doesn't fix broken Thumb1 variant of __udivsi3 !
Reviewers: weimingz, rengolin, compnerd
Subscribers: aemerson, dim
Differential Revision: https://reviews.llvm.org/D30938
Discussed with: mmel
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp')
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp | 894 |
1 files changed, 894 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp b/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp new file mode 100644 index 0000000..e761738 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp @@ -0,0 +1,894 @@ +//===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// This file implements classes for searching and anlyzing source code clones. +/// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/CloneDetection.h" + +#include "clang/AST/ASTContext.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/Lex/Lexer.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/MD5.h" +#include "llvm/Support/raw_ostream.h" + +using namespace clang; + +StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context, + unsigned StartIndex, unsigned EndIndex) + : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) { + assert(Stmt && "Stmt must not be a nullptr"); + assert(StartIndex < EndIndex && "Given array should not be empty"); + assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt"); +} + +StmtSequence::StmtSequence(const Stmt *Stmt, ASTContext &Context) + : S(Stmt), Context(&Context), StartIndex(0), EndIndex(0) {} + +StmtSequence::StmtSequence() + : S(nullptr), Context(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) + return false; + + const SourceManager &SM = Context->getSourceManager(); + + // Otherwise check if the start and end locations of the current sequence + // surround the other sequence. + bool StartIsInBounds = + SM.isBeforeInTranslationUnit(getStartLoc(), Other.getStartLoc()) || + getStartLoc() == Other.getStartLoc(); + if (!StartIsInBounds) + return false; + + bool EndIsInBounds = + SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) || + Other.getEndLoc() == getEndLoc(); + return EndIsInBounds; +} + +StmtSequence::iterator StmtSequence::begin() const { + if (!holdsSequence()) { + return &S; + } + auto CS = cast<CompoundStmt>(S); + return CS->body_begin() + StartIndex; +} + +StmtSequence::iterator StmtSequence::end() const { + if (!holdsSequence()) { + return reinterpret_cast<StmtSequence::iterator>(&S) + 1; + } + auto CS = cast<CompoundStmt>(S); + return CS->body_begin() + EndIndex; +} + +SourceLocation StmtSequence::getStartLoc() const { + return front()->getLocStart(); +} + +SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); } + +SourceRange StmtSequence::getSourceRange() const { + 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<VariableOccurence> Occurences; + /// List of referenced variables in the order of appearance. + /// Every item in this list is unique. + std::vector<const VarDecl *> 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<DeclRefExpr>(S)) { + if (auto VD = dyn_cast<VarDecl>(D->getDecl()->getCanonicalDecl())) + addVariableOccurence(VD, D); + } + + // Recursively check all children of the given statement. + for (const Stmt *Child : S->children()) { + addVariables(Child); + } + } + +public: + /// \brief Creates an VariablePattern object with information about the given + /// StmtSequence. + VariablePattern(const StmtSequence &Sequence) { + for (const Stmt *S : Sequence) + addVariables(S); + } + + /// \brief Counts the differences between this pattern and the given one. + /// \param Other The given VariablePattern to compare with. + /// \param FirstMismatch Output parameter that will be filled with information + /// about the first difference between the two patterns. This parameter + /// can be a nullptr, in which case it will be ignored. + /// \return Returns the number of differences between the pattern this object + /// is following and the given VariablePattern. + /// + /// For example, the following statements all have the same pattern and this + /// function would return zero: + /// + /// if (a < b) return a; return b; + /// if (x < y) return x; return y; + /// if (u2 < u1) return u2; return u1; + /// + /// But the following statement has a different pattern (note the changed + /// variables in the return statements) and would have two differences when + /// compared with one of the statements above. + /// + /// if (a < b) return b; return a; + /// + /// This function should only be called if the related statements of the given + /// pattern and the statements of this objects are clones of each other. + unsigned countPatternDifferences( + const VariablePattern &Other, + CloneDetector::SuspiciousClonePair *FirstMismatch = nullptr) { + unsigned NumberOfDifferences = 0; + + assert(Other.Occurences.size() == Occurences.size()); + for (unsigned i = 0; i < Occurences.size(); ++i) { + auto ThisOccurence = Occurences[i]; + auto OtherOccurence = Other.Occurences[i]; + if (ThisOccurence.KindID == OtherOccurence.KindID) + continue; + + ++NumberOfDifferences; + + // If FirstMismatch is not a nullptr, we need to store information about + // the first difference between the two patterns. + if (FirstMismatch == nullptr) + continue; + + // Only proceed if we just found the first difference as we only store + // information about the first difference. + if (NumberOfDifferences != 1) + continue; + + const VarDecl *FirstSuggestion = nullptr; + // If there is a variable available in the list of referenced variables + // which wouldn't break the pattern if it is used in place of the + // current variable, we provide this variable as the suggested fix. + if (OtherOccurence.KindID < Variables.size()) + FirstSuggestion = Variables[OtherOccurence.KindID]; + + // Store information about the first clone. + FirstMismatch->FirstCloneInfo = + CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo( + Variables[ThisOccurence.KindID], ThisOccurence.Mention, + FirstSuggestion); + + // Same as above but with the other clone. We do this for both clones as + // we don't know which clone is the one containing the unintended + // pattern error. + const VarDecl *SecondSuggestion = nullptr; + if (ThisOccurence.KindID < Other.Variables.size()) + SecondSuggestion = Other.Variables[ThisOccurence.KindID]; + + // Store information about the second clone. + FirstMismatch->SecondCloneInfo = + CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo( + Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention, + SecondSuggestion); + + // SuspiciousClonePair guarantees that the first clone always has a + // suggested variable associated with it. As we know that one of the two + // clones in the pair always has suggestion, we swap the two clones + // in case the first clone has no suggested variable which means that + // the second clone has a suggested variable and should be first. + if (!FirstMismatch->FirstCloneInfo.Suggestion) + std::swap(FirstMismatch->FirstCloneInfo, + FirstMismatch->SecondCloneInfo); + + // This ensures that we always have at least one suggestion in a pair. + assert(FirstMismatch->FirstCloneInfo.Suggestion); + } + + return NumberOfDifferences; + } +}; +} + +/// \brief Prints the macro name that contains the given SourceLocation into +/// the given raw_string_ostream. +static void printMacroName(llvm::raw_string_ostream &MacroStack, + ASTContext &Context, SourceLocation Loc) { + MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(), + Context.getLangOpts()); + + // Add an empty space at the end as a padding to prevent + // that macro names concatenate to the names of other macros. + MacroStack << " "; +} + +/// \brief Returns a string that represents all macro expansions that +/// expanded into the given SourceLocation. +/// +/// If 'getMacroStack(A) == getMacroStack(B)' is true, then the SourceLocations +/// A and B are expanded from the same macros in the same order. +static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) { + std::string MacroStack; + llvm::raw_string_ostream MacroStackStream(MacroStack); + SourceManager &SM = Context.getSourceManager(); + + // Iterate over all macros that expanded into the given SourceLocation. + while (Loc.isMacroID()) { + // Add the macro name to the stream. + printMacroName(MacroStackStream, Context, Loc); + Loc = SM.getImmediateMacroCallerLoc(Loc); + } + MacroStackStream.flush(); + return MacroStack; +} + +namespace { +/// \brief Collects the data of a single Stmt. +/// +/// This class defines what a code clone is: If it collects for two statements +/// the same data, then those two statements are considered to be clones of each +/// other. +/// +/// All collected data is forwarded to the given data consumer of the type T. +/// The data consumer class needs to provide a member method with the signature: +/// update(StringRef Str) +template <typename T> +class StmtDataCollector : public ConstStmtVisitor<StmtDataCollector<T>> { + + ASTContext &Context; + /// \brief The data sink to which all data is forwarded. + T &DataConsumer; + +public: + /// \brief Collects data of the given Stmt. + /// \param S The given statement. + /// \param Context The ASTContext of S. + /// \param DataConsumer The data sink to which all data is forwarded. + StmtDataCollector(const Stmt *S, ASTContext &Context, T &DataConsumer) + : Context(Context), DataConsumer(DataConsumer) { + this->Visit(S); + } + + // Below are utility methods for appending different data to the vector. + + void addData(CloneDetector::DataPiece Integer) { + DataConsumer.update( + StringRef(reinterpret_cast<char *>(&Integer), sizeof(Integer))); + } + + void addData(llvm::StringRef Str) { DataConsumer.update(Str); } + + void addData(const QualType &QT) { addData(QT.getAsString()); } + +// The functions below collect the class specific data of each Stmt subclass. + +// Utility macro for defining a visit method for a given class. This method +// calls back to the ConstStmtVisitor to visit all parent classes. +#define DEF_ADD_DATA(CLASS, CODE) \ + void Visit##CLASS(const CLASS *S) { \ + CODE; \ + ConstStmtVisitor<StmtDataCollector>::Visit##CLASS(S); \ + } + + DEF_ADD_DATA(Stmt, { + addData(S->getStmtClass()); + // This ensures that macro generated code isn't identical to macro-generated + // code. + addData(getMacroStack(S->getLocStart(), Context)); + addData(getMacroStack(S->getLocEnd(), Context)); + }) + DEF_ADD_DATA(Expr, { addData(S->getType()); }) + + //--- Builtin functionality ----------------------------------------------// + DEF_ADD_DATA(ArrayTypeTraitExpr, { addData(S->getTrait()); }) + DEF_ADD_DATA(ExpressionTraitExpr, { addData(S->getTrait()); }) + DEF_ADD_DATA(PredefinedExpr, { addData(S->getIdentType()); }) + DEF_ADD_DATA(TypeTraitExpr, { + addData(S->getTrait()); + for (unsigned i = 0; i < S->getNumArgs(); ++i) + addData(S->getArg(i)->getType()); + }) + + //--- Calls --------------------------------------------------------------// + DEF_ADD_DATA(CallExpr, { + // Function pointers don't have a callee and we just skip hashing it. + if (const FunctionDecl *D = S->getDirectCallee()) { + // If the function is a template specialization, we also need to handle + // the template arguments as they are not included in the qualified name. + if (auto Args = D->getTemplateSpecializationArgs()) { + std::string ArgString; + + // Print all template arguments into ArgString + llvm::raw_string_ostream OS(ArgString); + for (unsigned i = 0; i < Args->size(); ++i) { + Args->get(i).print(Context.getLangOpts(), OS); + // Add a padding character so that 'foo<X, XX>()' != 'foo<XX, X>()'. + OS << '\n'; + } + OS.flush(); + + addData(ArgString); + } + addData(D->getQualifiedNameAsString()); + } + }) + + //--- Exceptions ---------------------------------------------------------// + DEF_ADD_DATA(CXXCatchStmt, { addData(S->getCaughtType()); }) + + //--- C++ OOP Stmts ------------------------------------------------------// + DEF_ADD_DATA(CXXDeleteExpr, { + addData(S->isArrayFormAsWritten()); + addData(S->isGlobalDelete()); + }) + + //--- Casts --------------------------------------------------------------// + DEF_ADD_DATA(ObjCBridgedCastExpr, { addData(S->getBridgeKind()); }) + + //--- Miscellaneous Exprs ------------------------------------------------// + DEF_ADD_DATA(BinaryOperator, { addData(S->getOpcode()); }) + DEF_ADD_DATA(UnaryOperator, { addData(S->getOpcode()); }) + + //--- Control flow -------------------------------------------------------// + DEF_ADD_DATA(GotoStmt, { addData(S->getLabel()->getName()); }) + DEF_ADD_DATA(IndirectGotoStmt, { + if (S->getConstantTarget()) + addData(S->getConstantTarget()->getName()); + }) + DEF_ADD_DATA(LabelStmt, { addData(S->getDecl()->getName()); }) + DEF_ADD_DATA(MSDependentExistsStmt, { addData(S->isIfExists()); }) + DEF_ADD_DATA(AddrLabelExpr, { addData(S->getLabel()->getName()); }) + + //--- Objective-C --------------------------------------------------------// + DEF_ADD_DATA(ObjCIndirectCopyRestoreExpr, { addData(S->shouldCopy()); }) + DEF_ADD_DATA(ObjCPropertyRefExpr, { + addData(S->isSuperReceiver()); + addData(S->isImplicitProperty()); + }) + DEF_ADD_DATA(ObjCAtCatchStmt, { addData(S->hasEllipsis()); }) + + //--- Miscellaneous Stmts ------------------------------------------------// + DEF_ADD_DATA(CXXFoldExpr, { + addData(S->isRightFold()); + addData(S->getOperator()); + }) + DEF_ADD_DATA(GenericSelectionExpr, { + for (unsigned i = 0; i < S->getNumAssocs(); ++i) { + addData(S->getAssocType(i)); + } + }) + DEF_ADD_DATA(LambdaExpr, { + for (const LambdaCapture &C : S->captures()) { + addData(C.isPackExpansion()); + addData(C.getCaptureKind()); + if (C.capturesVariable()) + addData(C.getCapturedVar()->getType()); + } + addData(S->isGenericLambda()); + addData(S->isMutable()); + }) + DEF_ADD_DATA(DeclStmt, { + auto numDecls = std::distance(S->decl_begin(), S->decl_end()); + addData(static_cast<CloneDetector::DataPiece>(numDecls)); + for (const Decl *D : S->decls()) { + if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { + addData(VD->getType()); + } + } + }) + DEF_ADD_DATA(AsmStmt, { + addData(S->isSimple()); + addData(S->isVolatile()); + addData(S->generateAsmString(Context)); + for (unsigned i = 0; i < S->getNumInputs(); ++i) { + addData(S->getInputConstraint(i)); + } + for (unsigned i = 0; i < S->getNumOutputs(); ++i) { + addData(S->getOutputConstraint(i)); + } + for (unsigned i = 0; i < S->getNumClobbers(); ++i) { + addData(S->getClobber(i)); + } + }) + DEF_ADD_DATA(AttributedStmt, { + for (const Attr *A : S->getAttrs()) { + addData(std::string(A->getSpelling())); + } + }) +}; +} // end anonymous namespace + +namespace { +/// Generates CloneSignatures for a set of statements and stores the results in +/// a CloneDetector object. +class CloneSignatureGenerator { + + CloneDetector &CD; + ASTContext &Context; + + /// \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<llvm::MD5>(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; + } + + // Storage for the signatures of the direct child statements. This is only + // needed if the current statement is a CompoundStmt. + std::vector<CloneDetector::CloneSignature> ChildSignatures; + const CompoundStmt *CS = dyn_cast<const CompoundStmt>(S); + + // 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; + + // 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); + + // Add the collected data to the signature of the current statement. + Signature.Complexity += ChildSignature.Complexity; + Hash.update(StringRef(reinterpret_cast<char *>(&ChildSignature.Hash), + sizeof(ChildSignature.Hash))); + + // 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 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); + + // Create the final hash code for the current signature. + llvm::MD5::MD5Result HashResult; + Hash.final(HashResult); + + // 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))); + + // Save the signature for the current statement in the CloneDetector object. + CD.add(StmtSequence(S, Context), Signature); + + return Signature; + } + + /// \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<CloneDetector::CloneSignature> &ChildSignatures) { + + // FIXME: This function has quadratic runtime right now. Check if skipping + // this function for too long CompoundStmts is an option. + + // The length of the sub-sequence. We don't need to handle sequences with + // the length 1 as they are already handled in CollectData(). + for (unsigned Length = 2; Length <= CS->size(); ++Length) { + // The start index in the body of the CompoundStmt. We increase the + // position until the end of the sub-sequence reaches the end of the + // CompoundStmt body. + for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) { + // Create an empty signature and add the signatures of all selected + // child statements to it. + CloneDetector::CloneSignature SubSignature; + llvm::MD5 SubHash; + + for (unsigned i = Pos; i < Pos + Length; ++i) { + SubSignature.Complexity += ChildSignatures[i].Complexity; + size_t ChildHash = ChildSignatures[i].Hash; + + SubHash.update(StringRef(reinterpret_cast<char *>(&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); + } + } + } + +public: + explicit CloneSignatureGenerator(CloneDetector &CD, ASTContext &Context) + : CD(CD), Context(Context) {} + + /// \brief Generates signatures for all statements in the given function body. + void consumeCodeBody(const Stmt *S) { generateSignatures(S, ""); } +}; +} // end anonymous namespace + +void CloneDetector::analyzeCodeBody(const Decl *D) { + assert(D); + assert(D->hasBody()); + CloneSignatureGenerator Generator(*this, D->getASTContext()); + Generator.consumeCodeBody(D->getBody()); +} + +void CloneDetector::add(const StmtSequence &S, + const CloneSignature &Signature) { + Sequences.push_back(std::make_pair(Signature, S)); +} + +namespace { +/// \brief Returns true if and only if \p Stmt contains at least one other +/// sequence in the \p Group. +bool containsAnyInGroup(StmtSequence &Stmt, CloneDetector::CloneGroup &Group) { + for (StmtSequence &GroupStmt : Group.Sequences) { + if (Stmt.contains(GroupStmt)) + return true; + } + return false; +} + +/// \brief Returns true if and only if all sequences in \p OtherGroup are +/// contained by a sequence in \p Group. +bool containsGroup(CloneDetector::CloneGroup &Group, + CloneDetector::CloneGroup &OtherGroup) { + // We have less sequences in the current group than we have in the other, + // so we will never fulfill the requirement for returning true. This is only + // possible because we know that a sequence in Group can contain at most + // one sequence in OtherGroup. + if (Group.Sequences.size() < OtherGroup.Sequences.size()) + return false; + + for (StmtSequence &Stmt : Group.Sequences) { + if (!containsAnyInGroup(Stmt, OtherGroup)) + return false; + } + return true; +} +} // end anonymous namespace + +namespace { +/// \brief Wrapper around FoldingSetNodeID that it can be used as the template +/// argument of the StmtDataCollector. +class FoldingSetNodeIDWrapper { + + llvm::FoldingSetNodeID &FS; + +public: + FoldingSetNodeIDWrapper(llvm::FoldingSetNodeID &FS) : FS(FS) {} + + void update(StringRef Str) { FS.AddString(Str); } +}; +} // end anonymous namespace + +/// \brief Writes the relevant data from all statements and child statements +/// in the given StmtSequence into the given FoldingSetNodeID. +static void CollectStmtSequenceData(const StmtSequence &Sequence, + FoldingSetNodeIDWrapper &OutputData) { + for (const Stmt *S : Sequence) { + StmtDataCollector<FoldingSetNodeIDWrapper>(S, Sequence.getASTContext(), + OutputData); + + for (const Stmt *Child : S->children()) { + if (!Child) + continue; + + CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()), + OutputData); + } + } +} + +/// \brief Returns true if both sequences are clones of each other. +static bool areSequencesClones(const StmtSequence &LHS, + const StmtSequence &RHS) { + // We collect the data from all statements in the sequence as we did before + // when generating a hash value for each sequence. But this time we don't + // hash the collected data and compare the whole data set instead. This + // prevents any false-positives due to hash code collisions. + llvm::FoldingSetNodeID DataLHS, DataRHS; + FoldingSetNodeIDWrapper LHSWrapper(DataLHS); + FoldingSetNodeIDWrapper RHSWrapper(DataRHS); + + CollectStmtSequenceData(LHS, LHSWrapper); + CollectStmtSequenceData(RHS, RHSWrapper); + + 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<CloneDetector::CloneGroup> &Result, + const CloneDetector::CloneGroup &Group, + bool CheckVariablePattern) { + // We remove the Sequences one by one, so a list is more appropriate. + std::list<StmtSequence> 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; + } + + // If we weren't asked to check for a matching variable pattern in clone + // groups we can add the sequence now to the new clone group. + // If we were asked to check for matching variable pattern, we first have + // to check that there are no differences between the two patterns and + // only proceed if they match. + if (!CheckVariablePattern || + VariablePattern(*I).countPatternDifferences(PrototypeFeatures) == 0) { + FilteredGroup.Sequences.push_back(*I); + I = UnassignedSequences.erase(I); + continue; + } + + // We didn't found a matching variable pattern, so we continue with the + // next sequence. + ++I; + } + + // Add a valid clone group to the list of found clone groups. + if (!FilteredGroup.isValid()) + continue; + + Result.push_back(FilteredGroup); + } +} + +void CloneDetector::findClones(std::vector<CloneGroup> &Result, + unsigned MinGroupComplexity, + bool CheckPatterns) { + // A shortcut (and necessary for the for-loop later in this function). + if (Sequences.empty()) + return; + + // 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<CloneSignature, StmtSequence> LHS, + std::pair<CloneSignature, StmtSequence> RHS) { + return LHS.first.Hash < RHS.first.Hash; + }); + + std::vector<CloneGroup> 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; + + // 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; + } + + // Skip CloneSignatures that won't pass the complexity requirement. + if (Signature.first.Complexity < MinGroupComplexity) + continue; + + Group.Sequences.push_back(Signature.second); + } + + // 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; + + CloneGroups.push_back(Group); + } + + // Add every valid clone group that fulfills the complexity requirement. + for (const CloneGroup &Group : CloneGroups) { + createCloneGroups(Result, Group, CheckPatterns); + } + + std::vector<unsigned> 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; + + if (containsGroup(Result[j], Result[i])) { + IndexesToRemove.push_back(i); + break; + } + } + } + + // 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); + } +} + +void CloneDetector::findSuspiciousClones( + std::vector<CloneDetector::SuspiciousClonePair> &Result, + unsigned MinGroupComplexity) { + std::vector<CloneGroup> 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; + } + } + } + } +} |
