Index: include/clang/AST/DataCollection.h =================================================================== --- /dev/null +++ include/clang/AST/DataCollection.h @@ -0,0 +1,50 @@ +//===--- DatatCollection.h --------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares helper methods for collecting data from AST nodes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_DATACOLLECTION_H +#define LLVM_CLANG_AST_DATACOLLECTION_H + +#include "clang/AST/ASTContext.h" + +namespace clang { + +/// 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. +std::string getMacroStack(SourceLocation Loc, ASTContext &Context); + +/// Utility functions for adding data to some consumer. +/// The consumer must implement a method update(StringRef) +template +void addDataToConsumer(T &DataConsumer, llvm::StringRef Str) { + DataConsumer.update(Str); +} + +template void addDataToConsumer(T &DataConsumer, const QualType &QT) { + addDataToConsumer(DataConsumer, QT.getAsString()); +} + +template +typename std::enable_if< + std::is_integral::value || std::is_enum::value || + std::is_convertible::value // for llvm::hash_code + >::type +addDataToConsumer(T &DataConsumer, Type Data) { + DataConsumer.update(StringRef(reinterpret_cast(&Data), sizeof(Data))); +} + +} // end namespace clang + +#endif // LLVM_CLANG_AST_DATACOLLECTION_H Index: include/clang/Analysis/CloneDetection.h =================================================================== --- include/clang/Analysis/CloneDetection.h +++ include/clang/Analysis/CloneDetection.h @@ -15,11 +15,7 @@ #ifndef LLVM_CLANG_AST_CLONEDETECTION_H #define LLVM_CLANG_AST_CLONEDETECTION_H -#include "clang/AST/DeclTemplate.h" #include "clang/AST/StmtVisitor.h" -#include "clang/Basic/SourceLocation.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringRef.h" #include "llvm/Support/Regex.h" #include @@ -31,192 +27,6 @@ class ASTContext; class CompoundStmt; -namespace clone_detection { - -/// 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. -std::string getMacroStack(SourceLocation Loc, ASTContext &Context); - -/// 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 -class StmtDataCollector : public ConstStmtVisitor> { - - ASTContext &Context; - /// The data sink to which all data is forwarded. - T &DataConsumer; - -public: - /// 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); - } - - typedef unsigned DataPiece; - - // Below are utility methods for appending different data to the vector. - - void addData(DataPiece Integer) { - DataConsumer.update( - StringRef(reinterpret_cast(&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::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()' != 'foo()'. - 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(numDecls)); - for (const Decl *D : S->decls()) { - if (const VarDecl *VD = dyn_cast(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())); - } - }) -}; -} // namespace clone_detection - /// Identifies a list of statements. /// /// Can either identify a single arbitrary Stmt object, a continuous sequence of Index: lib/AST/CMakeLists.txt =================================================================== --- lib/AST/CMakeLists.txt +++ lib/AST/CMakeLists.txt @@ -20,6 +20,7 @@ CommentLexer.cpp CommentParser.cpp CommentSema.cpp + DataCollection.cpp Decl.cpp DeclarationName.cpp DeclBase.cpp Index: lib/AST/DataCollection.cpp =================================================================== --- /dev/null +++ lib/AST/DataCollection.cpp @@ -0,0 +1,48 @@ +//===-- DataCollection.cpp --------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/DataCollection.h" + +#include "clang/Lex/Lexer.h" + +namespace clang { + +/// 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 << " "; +} + +/// 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. +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; +} + +} // end namespace clang Index: lib/AST/StmtDataCollectors.inc =================================================================== --- /dev/null +++ lib/AST/StmtDataCollectors.inc @@ -0,0 +1,141 @@ +// The functions below collect the class specific data of each Stmt subclass. + +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()' != 'foo()'. + OS << '\n'; + } + OS.flush(); + + addData(ArgString); + } + addData(D->getQualifiedNameAsString()); + } +}) + +//--- Value references ---------------------------------------------------// +DEF_ADD_DATA(DeclRefExpr, + { addData(S->getDecl()->getQualifiedNameAsString()); }) +DEF_ADD_DATA(MemberExpr, + { addData(S->getMemberDecl()->getQualifiedNameAsString()); }) + +//--- Literals -----------------------------------------------------------// +DEF_ADD_DATA(IntegerLiteral, { addData(llvm::hash_value(S->getValue())); }) +DEF_ADD_DATA(FloatingLiteral, { addData(llvm::hash_value(S->getValue())); }) +DEF_ADD_DATA(StringLiteral, { addData(S->getString()); }) +DEF_ADD_DATA(CXXBoolLiteralExpr, { addData(S->getValue()); }) +DEF_ADD_DATA(CharacterLiteral, { addData(S->getValue()); }) + +//--- 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(numDecls)); + for (const Decl *D : S->decls()) { + if (const VarDecl *VD = dyn_cast(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())); + } +}) +#undef DEF_ADD_DATA Index: lib/Analysis/CloneDetection.cpp =================================================================== --- lib/Analysis/CloneDetection.cpp +++ lib/Analysis/CloneDetection.cpp @@ -13,16 +13,12 @@ #include "clang/Analysis/CloneDetection.h" -#include "clang/AST/ASTContext.h" -#include "clang/AST/RecursiveASTVisitor.h" -#include "clang/AST/Stmt.h" -#include "clang/Lex/Lexer.h" +#include "clang/AST/DataCollection.h" +#include "clang/AST/DeclTemplate.h" #include "llvm/Support/MD5.h" -#include "llvm/Support/raw_ostream.h" #include "llvm/Support/Path.h" using namespace clang; -using namespace clang::clone_detection; StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex, unsigned EndIndex) @@ -91,34 +87,6 @@ return SourceRange(getStartLoc(), getEndLoc()); } -/// 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 << " "; -} - -std::string clone_detection::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; -} - void CloneDetector::analyzeCodeBody(const Decl *D) { assert(D); assert(D->hasBody()); @@ -201,6 +169,59 @@ return false; } +/// 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 +class CloneTypeIIStmtDataCollector + : public ConstStmtVisitor> { + ASTContext &Context; + /// The data sink to which all data is forwarded. + T &DataConsumer; + + template void addData(Ty Data) { + addDataToConsumer(DataConsumer, Data); + } + +public: + CloneTypeIIStmtDataCollector(const Stmt *S, ASTContext &Context, + T &DataConsumer) + : Context(Context), DataConsumer(DataConsumer) { + this->Visit(S); + } + +// Define a visit method for each class to collect data and subsequently visit +// all parent classes. This uses a template so that custom visit methods by us +// take precedence. +#define DEF_ADD_DATA(CLASS, CODE) \ + template Dummy Visit##CLASS(const CLASS *S) { \ + CODE; \ + ConstStmtVisitor>::Visit##CLASS(S); \ + } + +#include "../AST/StmtDataCollectors.inc" + +// Override the definition for some visitors. +#define SKIP(CLASS) \ + void Visit##CLASS(const CLASS *S) { \ + ConstStmtVisitor>::Visit##CLASS(S); \ + } + SKIP(DeclRefExpr) + SKIP(MemberExpr) + SKIP(IntegerLiteral) + SKIP(FloatingLiteral) + SKIP(StringLiteral) + SKIP(CXXBoolLiteralExpr) + SKIP(CharacterLiteral) +#undef SKIP +}; + static size_t createHash(llvm::MD5 &Hash) { size_t HashCode; @@ -222,7 +243,7 @@ llvm::MD5 Hash; ASTContext &Context = D->getASTContext(); - StmtDataCollector(S, Context, Hash); + CloneTypeIIStmtDataCollector(S, Context, Hash); auto CS = dyn_cast(S); SmallVector ChildHashes; @@ -288,8 +309,8 @@ static void CollectStmtSequenceData(const StmtSequence &Sequence, FoldingSetNodeIDWrapper &OutputData) { for (const Stmt *S : Sequence) { - StmtDataCollector(S, Sequence.getASTContext(), - OutputData); + CloneTypeIIStmtDataCollector( + S, Sequence.getASTContext(), OutputData); for (const Stmt *Child : S->children()) { if (!Child)