Artem, I think you broke the build. Could you take a look please?
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer/builds/11051 http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer/builds/11051/steps/build%20clang/logs/stdio [80/140] Building CXX object tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/clangStaticAnalyzerCheckers.dir/CloneChecker.cpp.o FAILED: tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/clangStaticAnalyzerCheckers.dir/CloneChecker.cpp.o /usr/bin/c++ -DCLANG_ENABLE_ARCMT -DCLANG_ENABLE_OBJC_REWRITER -DCLANG_ENABLE_STATIC_ANALYZER -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/clang/lib/StaticAnalyzer/Checkers -I/mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers -I/mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/tools/clang/include -Itools/clang/include -Iinclude -I/mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/include -fPIC -fvisibility-inlines-hidden -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wdelete-non-virtual-dtor -Wno-comment -Werror=date-time -std=c++11 -ffunction-sections -fdata-sections -fno-common -Woverloaded-virtual -fno-strict-aliasing -O3 -DNDEBUG -fno-exceptions -fno-rtti -MMD -MT tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/clangStaticAnalyzerCheckers.dir/CloneChecker.cpp.o -MF tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/clangStaticAnalyzerCheckers.dir/CloneChecker.cpp.o.d -o tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/clangStaticAnalyzerCheckers.dir/CloneChecker.cpp.o -c /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp/mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp:29:25: error: declaration of ‘clang::CloneDetector {anonymous}::CloneChecker::CloneDetector’ [-fpermissive] mutable CloneDetector CloneDetector; ^ In file included from /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/CloneChecker.cpp:17:0: /mnt/b/sanitizer-buildbot5/sanitizer-x86_64-linux-fuzzer/build/llvm/tools/clang/include/clang/Analysis/CloneDetection.h:158:7: error: changes meaning of ‘CloneDetector’ from ‘class clang::CloneDetector’ [-fpermissive] class CloneDetector { ^ On Tue, Jul 26, 2016 at 11:28 AM Artem Dergachev via cfe-commits < cfe-commits@lists.llvm.org> wrote: > Author: dergachev > Date: Tue Jul 26 13:13:12 2016 > New Revision: 276782 > > URL: http://llvm.org/viewvc/llvm-project?rev=276782&view=rev > Log: > [analyzer] Add basic capabilities to detect source code clones. > > This patch adds the CloneDetector class which allows searching source code > for clones. > > For every statement or group of statements within a compound statement, > CloneDetector computes a hash value, and finds clones by detecting > identical hash values. > > This initial patch only provides a simple hashing mechanism > that hashes the kind of each sub-statement. > > This patch also adds CloneChecker - a simple static analyzer checker > that uses CloneDetector to report copy-pasted code. > > Patch by Raphael Isemann! > > Differential Revision: https://reviews.llvm.org/D20795 > > Added: > cfe/trunk/include/clang/Analysis/CloneDetection.h > cfe/trunk/lib/Analysis/CloneDetection.cpp > cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp > cfe/trunk/test/Analysis/copypaste/ > cfe/trunk/test/Analysis/copypaste/blocks.cpp > cfe/trunk/test/Analysis/copypaste/false-positives.cpp > cfe/trunk/test/Analysis/copypaste/functions.cpp > cfe/trunk/test/Analysis/copypaste/objc-methods.m > cfe/trunk/test/Analysis/copypaste/sub-sequences.cpp > Modified: > cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td > cfe/trunk/lib/Analysis/CMakeLists.txt > cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt > > Added: cfe/trunk/include/clang/Analysis/CloneDetection.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Analysis/CloneDetection.h?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/include/clang/Analysis/CloneDetection.h (added) > +++ cfe/trunk/include/clang/Analysis/CloneDetection.h Tue Jul 26 13:13:12 > 2016 > @@ -0,0 +1,235 @@ > +//===--- CloneDetection.h - 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. > +// > > +//===----------------------------------------------------------------------===// > +/// > +/// /file > +/// This file defines classes for searching and anlyzing source code > clones. > +/// > > +//===----------------------------------------------------------------------===// > + > +#ifndef LLVM_CLANG_AST_CLONEDETECTION_H > +#define LLVM_CLANG_AST_CLONEDETECTION_H > + > +#include "clang/Basic/SourceLocation.h" > +#include "llvm/ADT/StringMap.h" > + > +#include <vector> > + > +namespace clang { > + > +class Stmt; > +class Decl; > +class ASTContext; > +class CompoundStmt; > + > +/// \brief Identifies a list of statements. > +/// > +/// Can either identify a single arbitrary Stmt object, a continuous > sequence of > +/// child statements inside a CompoundStmt or no statements at all. > +class StmtSequence { > + /// If this object identifies a sequence of statements inside a > CompoundStmt, > + /// S points to this CompoundStmt. If this object only identifies a > single > + /// Stmt, then S is a pointer to this Stmt. > + const Stmt *S; > + > + /// The related ASTContext for S. > + ASTContext *Context; > + > + /// If EndIndex is non-zero, then S is a CompoundStmt and this > StmtSequence > + /// instance is representing the CompoundStmt children inside the array > + /// [StartIndex, EndIndex). > + unsigned StartIndex; > + unsigned EndIndex; > + > +public: > + /// \brief Constructs a StmtSequence holding multiple statements. > + /// > + /// The resulting StmtSequence identifies a continuous sequence of > statements > + /// in the body of the given CompoundStmt. Which statements of the body > should > + /// be identified needs to be specified by providing a start and end > index > + /// that describe a non-empty sub-array in the body of the given > CompoundStmt. > + /// > + /// \param Stmt A CompoundStmt that contains all statements in its body. > + /// \param Context The ASTContext for the given CompoundStmt. > + /// \param StartIndex The inclusive start index in the children array of > + /// \p Stmt > + /// \param EndIndex The exclusive end index in the children array of \p > Stmt. > + StmtSequence(const CompoundStmt *Stmt, ASTContext &Context, > + unsigned StartIndex, unsigned EndIndex); > + > + /// \brief Constructs a StmtSequence holding a single statement. > + /// > + /// \param Stmt An arbitrary Stmt. > + /// \param Context The ASTContext for the given Stmt. > + StmtSequence(const Stmt *Stmt, ASTContext &Context); > + > + /// \brief Constructs an empty StmtSequence. > + StmtSequence(); > + > + typedef const Stmt *const *iterator; > + > + /// Returns an iterator pointing to the first statement in this > sequence. > + iterator begin() const; > + > + /// Returns an iterator pointing behind the last statement in this > sequence. > + iterator end() const; > + > + /// Returns the first statement in this sequence. > + /// > + /// This method should only be called on a non-empty StmtSequence > object. > + const Stmt *front() const { > + assert(!empty()); > + return begin()[0]; > + } > + > + /// Returns the last statement in this sequence. > + /// > + /// This method should only be called on a non-empty StmtSequence > object. > + const Stmt *back() const { > + assert(!empty()); > + return begin()[size() - 1]; > + } > + > + /// Returns the number of statements this object holds. > + unsigned size() const { > + if (holdsSequence()) > + return EndIndex - StartIndex; > + if (S == nullptr) > + return 0; > + return 1; > + } > + > + /// Returns true if and only if this StmtSequence contains no > statements. > + bool empty() const { return size() == 0; } > + > + /// Returns the related ASTContext for the stored Stmts. > + ASTContext &getASTContext() const { > + assert(Context); > + return *Context; > + } > + > + /// Returns true if this objects holds a list of statements. > + bool holdsSequence() const { return EndIndex != 0; } > + > + /// Returns the start sourcelocation of the first statement in this > sequence. > + /// > + /// This method should only be called on a non-empty StmtSequence > object. > + SourceLocation getStartLoc() const; > + > + /// Returns the end sourcelocation of the last statement in this > sequence. > + /// > + /// This method should only be called on a non-empty StmtSequence > object. > + SourceLocation getEndLoc() const; > + > + bool operator==(const StmtSequence &Other) const { > + return std::tie(S, StartIndex, EndIndex) == > + std::tie(Other.S, Other.StartIndex, Other.EndIndex); > + } > + > + bool operator!=(const StmtSequence &Other) const { > + return std::tie(S, StartIndex, EndIndex) != > + std::tie(Other.S, Other.StartIndex, Other.EndIndex); > + } > + > + /// Returns true if and only if this sequence covers a source range that > + /// contains the source range of the given sequence \p Other. > + /// > + /// This method should only be called on a non-empty StmtSequence object > + /// and passed a non-empty StmtSequence object. > + bool contains(const StmtSequence &Other) const; > +}; > + > +/// \brief Searches for clones in source code. > +/// > +/// First, this class needs a translation unit which is passed via > +/// \p analyzeTranslationUnit . It will then generate and store search > data > +/// for all statements inside the given translation unit. > +/// Afterwards the generated data can be used to find code clones by > calling > +/// \p findClones . > +/// > +/// This class only searches for clones in exectuable source code > +/// (e.g. function bodies). Other clones (e.g. cloned comments or > declarations) > +/// are not supported. > +class CloneDetector { > +public: > + /// Holds the data about a StmtSequence that is needed during the > search for > + /// code clones. > + struct CloneSignature { > + /// \brief Holds all relevant data of a StmtSequence. > + /// > + /// If this variable is equal for two different StmtSequences, then > they can > + /// be considered clones of each other. > + std::vector<unsigned> Data; > + > + /// \brief The complexity of the StmtSequence. > + /// > + /// This scalar value serves as a simple way of filtering clones that > are > + /// too small to be reported. A greater value indicates that the > related > + /// StmtSequence is probably more interesting to the user. > + unsigned Complexity; > + > + /// \brief Creates an empty CloneSignature without any data. > + CloneSignature() : Complexity(1) {} > + > + CloneSignature(const std::vector<unsigned> &Data, unsigned Complexity) > + : Data(Data), Complexity(Complexity) {} > + > + /// \brief Adds the data from the given CloneSignature to this one. > + void add(const CloneSignature &Other) { > + Data.insert(Data.end(), Other.Data.begin(), Other.Data.end()); > + Complexity += Other.Complexity; > + } > + }; > + > + /// Holds group of StmtSequences that are clones of each other and the > + /// complexity value (see CloneSignature::Complexity) that all stored > + /// StmtSequences have in common. > + struct CloneGroup { > + std::vector<StmtSequence> Sequences; > + unsigned Complexity; > + > + CloneGroup(const StmtSequence &Seq, unsigned Complexity) > + : Complexity(Complexity) { > + Sequences.push_back(Seq); > + } > + > + /// \brief Returns false if and only if this group should be skipped > when > + /// searching for clones. > + bool isValid() const { > + // A clone group with only one member makes no sense, so we skip > them. > + return Sequences.size() > 1; > + } > + }; > + > + /// \brief Generates and stores search data for all statements in the > body of > + /// the given Decl. > + void analyzeCodeBody(const Decl *D); > + > + /// \brief Stores the CloneSignature to allow future querying. > + void add(const StmtSequence &S, const CloneSignature &Signature); > + > + /// \brief Searches the provided statements for clones. > + /// > + /// \param Result Output parameter that is filled with a list of found > + /// clone groups. Each group contains multiple > StmtSequences > + /// that were identified to be clones of each other. > + /// \param MinGroupComplexity Only return clones which have at least > this > + /// complexity value. > + void findClones(std::vector<CloneGroup> &Result, unsigned > MinGroupComplexity); > + > +private: > + /// Stores all found clone groups including invalid groups with only a > single > + /// statement. > + std::vector<CloneGroup> CloneGroups; > + /// Maps search data to its related index in the \p CloneGroups vector. > + llvm::StringMap<std::size_t> CloneGroupIndexes; > +}; > + > +} // end namespace clang > + > +#endif // LLVM_CLANG_AST_CLONEDETECTION_H > > Modified: cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td?rev=276782&r1=276781&r2=276782&view=diff > > ============================================================================== > --- cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td (original) > +++ cfe/trunk/include/clang/StaticAnalyzer/Checkers/Checkers.td Tue Jul 26 > 13:13:12 2016 > @@ -77,6 +77,8 @@ def MPI : Package<"mpi">, InPackage<OptI > def LLVM : Package<"llvm">; > def Debug : Package<"debug">; > > +def CloneDetectionAlpha : Package<"clone">, InPackage<Alpha>, Hidden; > + > > > //===----------------------------------------------------------------------===// > // Core Checkers. > > > //===----------------------------------------------------------------------===// > @@ -661,3 +663,17 @@ def BugHashDumper : Checker<"DumpBugHash > DescFile<"DebugCheckers.cpp">; > > } // end "debug" > + > + > > +//===----------------------------------------------------------------------===// > +// Clone Detection > > +//===----------------------------------------------------------------------===// > + > +let ParentPackage = CloneDetectionAlpha in { > + > +def CloneChecker : Checker<"CloneChecker">, > + HelpText<"Reports similar pieces of code.">, > + DescFile<"CloneChecker.cpp">; > + > +} // end "clone" > + > > Modified: cfe/trunk/lib/Analysis/CMakeLists.txt > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/CMakeLists.txt?rev=276782&r1=276781&r2=276782&view=diff > > ============================================================================== > --- cfe/trunk/lib/Analysis/CMakeLists.txt (original) > +++ cfe/trunk/lib/Analysis/CMakeLists.txt Tue Jul 26 13:13:12 2016 > @@ -9,6 +9,7 @@ add_clang_library(clangAnalysis > CFGReachabilityAnalysis.cpp > CFGStmtMap.cpp > CallGraph.cpp > + CloneDetection.cpp > CocoaConventions.cpp > Consumed.cpp > CodeInjector.cpp > > Added: cfe/trunk/lib/Analysis/CloneDetection.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/CloneDetection.cpp?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/lib/Analysis/CloneDetection.cpp (added) > +++ cfe/trunk/lib/Analysis/CloneDetection.cpp Tue Jul 26 13:13:12 2016 > @@ -0,0 +1,277 @@ > +//===--- 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 "llvm/ADT/StringRef.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 &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(); } > + > +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. > + /// \return The CloneSignature of the root statement. > + CloneDetector::CloneSignature generateSignatures(const Stmt *S) { > + // Create an empty signature that will be filled in this method. > + CloneDetector::CloneSignature Signature; > + > + // The only relevant data for now is the class of the statement. > + // TODO: Collect statement class specific data. > + Signature.Data.push_back(S->getStmtClass()); > + > + // 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. > + auto ChildSignature = generateSignatures(Child); > + > + // Add the collected data to the signature of the current statement. > + Signature.add(ChildSignature); > + > + // 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); > + > + // 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; > + > + for (unsigned i = Pos; i < Pos + Length; ++i) { > + SubSignature.add(ChildSignatures[i]); > + } > + > + // 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) { > + // StringMap only works with StringRefs, so we create one for our data > vector. > + auto &Data = Signature.Data; > + StringRef DataRef = StringRef(reinterpret_cast<const char > *>(Data.data()), > + Data.size() * sizeof(unsigned)); > + > + // Search with the help of the signature if we already have encountered > a > + // clone of the given StmtSequence. > + auto I = CloneGroupIndexes.find(DataRef); > + if (I == CloneGroupIndexes.end()) { > + // We haven't found an existing clone group, so we create a new clone > group > + // for this StmtSequence and store the index of it in our search map. > + CloneGroupIndexes[DataRef] = CloneGroups.size(); > + CloneGroups.emplace_back(S, Signature.Complexity); > + return; > + } > + > + // We have found an existing clone group and can expand it with the > given > + // StmtSequence. > + CloneGroups[I->getValue()].Sequences.push_back(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 > + > +void CloneDetector::findClones(std::vector<CloneGroup> &Result, > + unsigned MinGroupComplexity) { > + // Add every valid clone group that fulfills the complexity requirement. > + for (const CloneGroup &Group : CloneGroups) { > + if (Group.isValid() && Group.Complexity >= MinGroupComplexity) { > + Result.push_back(Group); > + } > + } > + > + 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); > + } > +} > > Modified: cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt?rev=276782&r1=276781&r2=276782&view=diff > > ============================================================================== > --- cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt (original) > +++ cfe/trunk/lib/StaticAnalyzer/Checkers/CMakeLists.txt Tue Jul 26 > 13:13:12 2016 > @@ -22,6 +22,7 @@ add_clang_library(clangStaticAnalyzerChe > CheckerDocumentation.cpp > ChrootChecker.cpp > ClangCheckers.cpp > + CloneChecker.cpp > CXXSelfAssignmentChecker.cpp > DeadStoresChecker.cpp > DebugCheckers.cpp > > Added: cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp (added) > +++ cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp Tue Jul 26 > 13:13:12 2016 > @@ -0,0 +1,96 @@ > +//===--- CloneChecker.cpp - Clone detection checker -------------*- C++ > -*-===// > +// > +// The LLVM Compiler Infrastructure > +// > +// This file is distributed under the University of Illinois Open Source > +// License. See LICENSE.TXT for details. > +// > > +//===----------------------------------------------------------------------===// > +/// > +/// \file > +/// CloneChecker is a checker that reports clones in the current > translation > +/// unit. > +/// > > +//===----------------------------------------------------------------------===// > + > +#include "ClangSACheckers.h" > +#include "clang/Analysis/CloneDetection.h" > +#include "clang/Basic/Diagnostic.h" > +#include "clang/StaticAnalyzer/Core/Checker.h" > +#include "clang/StaticAnalyzer/Core/CheckerManager.h" > +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" > + > +using namespace clang; > +using namespace ento; > + > +namespace { > +class CloneChecker > + : public Checker<check::ASTCodeBody, check::EndOfTranslationUnit> { > + mutable CloneDetector CloneDetector; > + > +public: > + void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr, > + BugReporter &BR) const; > + > + void checkEndOfTranslationUnit(const TranslationUnitDecl *TU, > + AnalysisManager &Mgr, BugReporter &BR) > const; > +}; > +} // end anonymous namespace > + > +void CloneChecker::checkASTCodeBody(const Decl *D, AnalysisManager &Mgr, > + BugReporter &BR) const { > + // Every statement that should be included in the search for clones > needs to > + // be passed to the CloneDetector. > + CloneDetector.analyzeCodeBody(D); > +} > + > +void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl > *TU, > + AnalysisManager &Mgr, > + BugReporter &BR) const { > + // At this point, every statement in the translation unit has been > analyzed by > + // the CloneDetector. The only thing left to do is to report the found > clones. > + > + int MinComplexity = Mgr.getAnalyzerOptions().getOptionAsInteger( > + "MinimumCloneComplexity", 10, this); > + > + assert(MinComplexity >= 0); > + > + SourceManager &SM = BR.getSourceManager(); > + > + std::vector<CloneDetector::CloneGroup> CloneGroups; > + CloneDetector.findClones(CloneGroups, MinComplexity); > + > + DiagnosticsEngine &DiagEngine = Mgr.getDiagnostic(); > + > + unsigned WarnID = DiagEngine.getCustomDiagID(DiagnosticsEngine::Warning, > + "Detected code clone."); > + > + unsigned NoteID = DiagEngine.getCustomDiagID(DiagnosticsEngine::Note, > + "Related code clone is > here."); > + > + for (CloneDetector::CloneGroup &Group : CloneGroups) { > + // For readability reasons we sort the clones by line numbers. > + std::sort(Group.Sequences.begin(), Group.Sequences.end(), > + [&SM](const StmtSequence &LHS, const StmtSequence &RHS) { > + return SM.isBeforeInTranslationUnit(LHS.getStartLoc(), > + RHS.getStartLoc()) && > + SM.isBeforeInTranslationUnit(LHS.getEndLoc(), > + RHS.getEndLoc()); > + }); > + > + // We group the clones by printing the first as a warning and all > others > + // as a note. > + DiagEngine.Report(Group.Sequences.front().getStartLoc(), WarnID); > + for (unsigned i = 1; i < Group.Sequences.size(); ++i) { > + DiagEngine.Report(Group.Sequences[i].getStartLoc(), NoteID); > + } > + } > +} > + > > +//===----------------------------------------------------------------------===// > +// Register CloneChecker > > +//===----------------------------------------------------------------------===// > + > +void ento::registerCloneChecker(CheckerManager &Mgr) { > + Mgr.registerChecker<CloneChecker>(); > +} > > Added: cfe/trunk/test/Analysis/copypaste/blocks.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/copypaste/blocks.cpp?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/test/Analysis/copypaste/blocks.cpp (added) > +++ cfe/trunk/test/Analysis/copypaste/blocks.cpp Tue Jul 26 13:13:12 2016 > @@ -0,0 +1,19 @@ > +// RUN: %clang_cc1 -analyze -fblocks -std=c++11 > -analyzer-checker=alpha.clone.CloneChecker -verify %s > + > +// This tests if we search for clones in blocks. > + > +void log(); > + > +auto BlockA = ^(int a, int b){ // expected-warning{{Detected code clone.}} > + log(); > + if (a > b) > + return a; > + return b; > +}; > + > +auto BlockB = ^(int a, int b){ // expected-note{{Related code clone is > here.}} > + log(); > + if (a > b) > + return a; > + return b; > +}; > > Added: cfe/trunk/test/Analysis/copypaste/false-positives.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/copypaste/false-positives.cpp?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/test/Analysis/copypaste/false-positives.cpp (added) > +++ cfe/trunk/test/Analysis/copypaste/false-positives.cpp Tue Jul 26 > 13:13:12 2016 > @@ -0,0 +1,29 @@ > +// RUN: %clang_cc1 -analyze -std=c++11 > -analyzer-checker=alpha.clone.CloneChecker -verify %s > + > +// This test contains false-positive reports from the CloneChecker that > need to > +// be fixed. > + > +void log(); > + > +int max(int a, int b) { // expected-warning{{Detected code clone.}} > + log(); > + if (a > b) > + return a; > + return b; > +} > + > +// FIXME: Detect different binary operator kinds. > +int min1(int a, int b) { // expected-note{{Related code clone is here.}} > + log(); > + if (a < b) > + return a; > + return b; > +} > + > +// FIXME: Detect different variable patterns. > +int min2(int a, int b) { // expected-note{{Related code clone is here.}} > + log(); > + if (b > a) > + return a; > + return b; > +} > > Added: cfe/trunk/test/Analysis/copypaste/functions.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/copypaste/functions.cpp?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/test/Analysis/copypaste/functions.cpp (added) > +++ cfe/trunk/test/Analysis/copypaste/functions.cpp Tue Jul 26 13:13:12 > 2016 > @@ -0,0 +1,25 @@ > +// RUN: %clang_cc1 -analyze -std=c++11 > -analyzer-checker=alpha.clone.CloneChecker -verify %s > + > +// This tests if we search for clones in functions. > + > +void log(); > + > +int max(int a, int b) { // expected-warning{{Detected code clone.}} > + log(); > + if (a > b) > + return a; > + return b; > +} > + > +int maxClone(int x, int y) { // expected-note{{Related code clone is > here.}} > + log(); > + if (x > y) > + return x; > + return y; > +} > + > +// Functions below are not clones and should not be reported. > + > +int foo(int a, int b) { // no-warning > + return a + b; > +} > > Added: cfe/trunk/test/Analysis/copypaste/objc-methods.m > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/copypaste/objc-methods.m?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/test/Analysis/copypaste/objc-methods.m (added) > +++ cfe/trunk/test/Analysis/copypaste/objc-methods.m Tue Jul 26 13:13:12 > 2016 > @@ -0,0 +1,27 @@ > +// RUN: %clang_cc1 -analyze -Wno-objc-root-class > -analyzer-checker=alpha.clone.CloneChecker -verify %s > + > +// This tests if we search for clones in Objective-C methods. > + > +@interface A > +- (int) setOk : (int) a : (int) b; > +@end > + > +@implementation A > +- (int) setOk : (int) a : (int) b { // expected-warning{{Detected code > clone.}} > + if (a > b) > + return a; > + return b; > +} > +@end > + > +@interface B > +- (int) setOk : (int) a : (int) b; > +@end > + > +@implementation B > +- (int) setOk : (int) a : (int) b { // expected-note{{Related code clone > is here.}} > + if (a > b) > + return a; > + return b; > +} > +@end > > Added: cfe/trunk/test/Analysis/copypaste/sub-sequences.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/copypaste/sub-sequences.cpp?rev=276782&view=auto > > ============================================================================== > --- cfe/trunk/test/Analysis/copypaste/sub-sequences.cpp (added) > +++ cfe/trunk/test/Analysis/copypaste/sub-sequences.cpp Tue Jul 26 > 13:13:12 2016 > @@ -0,0 +1,27 @@ > +// RUN: %clang_cc1 -analyze -std=c++11 > -analyzer-checker=alpha.clone.CloneChecker -verify %s > + > +// This tests if sub-sequences can match with normal sequences. > + > +void log2(int a); > +void log(); > + > +int max(int a, int b) { > + log2(a); > + log(); // expected-warning{{Detected code clone.}} > + if (a > b) > + return a; > + return b; > +} > + > +int maxClone(int a, int b) { > + log(); // expected-note{{Related code clone is here.}} > + if (a > b) > + return a; > + return b; > +} > + > +// Functions below are not clones and should not be reported. > + > +int foo(int a, int b) { // no-warning > + return a + b; > +} > > > _______________________________________________ > cfe-commits mailing list > cfe-commits@lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits > -- Mike Sent from phone
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
