summaryrefslogtreecommitdiff
path: root/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/AnalysisDeclContext.cpp2
-rw-r--r--lib/Analysis/CFG.cpp224
-rw-r--r--lib/Analysis/CloneDetection.cpp217
3 files changed, 204 insertions, 239 deletions
diff --git a/lib/Analysis/AnalysisDeclContext.cpp b/lib/Analysis/AnalysisDeclContext.cpp
index 7c0f5543da040..ec15f34fb231d 100644
--- a/lib/Analysis/AnalysisDeclContext.cpp
+++ b/lib/Analysis/AnalysisDeclContext.cpp
@@ -67,6 +67,7 @@ AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
bool addImplicitDtors,
bool addInitializers,
bool addTemporaryDtors,
+ bool addLifetime,
bool synthesizeBodies,
bool addStaticInitBranch,
bool addCXXNewAllocator,
@@ -77,6 +78,7 @@ AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
cfgBuildOptions.AddImplicitDtors = addImplicitDtors;
cfgBuildOptions.AddInitializers = addInitializers;
cfgBuildOptions.AddTemporaryDtors = addTemporaryDtors;
+ cfgBuildOptions.AddLifetime = addLifetime;
cfgBuildOptions.AddStaticInitBranches = addStaticInitBranch;
cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
}
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp
index 2a2b3d73b5caf..6a77455edeef6 100644
--- a/lib/Analysis/CFG.cpp
+++ b/lib/Analysis/CFG.cpp
@@ -233,6 +233,7 @@ public:
}
int distance(const_iterator L);
+ const_iterator shared_parent(const_iterator L);
};
friend class const_iterator;
@@ -275,6 +276,30 @@ int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
return D;
}
+/// Calculates the closest parent of this iterator
+/// that is in a scope reachable through the parents of L.
+/// I.e. when using 'goto' from this to L, the lifetime of all variables
+/// between this and shared_parent(L) end.
+LocalScope::const_iterator
+LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {
+ llvm::SmallPtrSet<const LocalScope *, 4> ScopesOfL;
+ while (true) {
+ ScopesOfL.insert(L.Scope);
+ if (L == const_iterator())
+ break;
+ L = L.Scope->Prev;
+ }
+
+ const_iterator F = *this;
+ while (true) {
+ if (ScopesOfL.count(F.Scope))
+ return F;
+ assert(F != const_iterator() &&
+ "L iterator is not reachable from F iterator.");
+ F = F.Scope->Prev;
+ }
+}
+
/// Structure for specifying position in CFG during its build process. It
/// consists of CFGBlock that specifies position in CFG and
/// LocalScope::const_iterator that specifies position in LocalScope graph.
@@ -579,6 +604,10 @@ private:
CFGBlock *addInitializer(CXXCtorInitializer *I);
void addAutomaticObjDtors(LocalScope::const_iterator B,
LocalScope::const_iterator E, Stmt *S);
+ void addLifetimeEnds(LocalScope::const_iterator B,
+ LocalScope::const_iterator E, Stmt *S);
+ void addAutomaticObjHandling(LocalScope::const_iterator B,
+ LocalScope::const_iterator E, Stmt *S);
void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
// Local scopes creation.
@@ -619,6 +648,10 @@ private:
B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
}
+ void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
+ B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
+ }
+
void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
}
@@ -626,6 +659,10 @@ private:
void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
LocalScope::const_iterator B, LocalScope::const_iterator E);
+ void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
+ LocalScope::const_iterator B,
+ LocalScope::const_iterator E);
+
void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),
cfg->getBumpVectorContext());
@@ -957,7 +994,8 @@ private:
return TryResult();
}
-
+
+ bool hasTrivialDestructor(VarDecl *VD);
};
inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
@@ -1031,6 +1069,9 @@ std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
assert(Succ == &cfg->getExit());
Block = nullptr; // the EXIT block is empty. Create all other blocks lazily.
+ assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
+ "AddImplicitDtors and AddLifetime cannot be used at the same time");
+
if (BuildOpts.AddImplicitDtors)
if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
addImplicitDtorsForDestructor(DD);
@@ -1067,6 +1108,8 @@ std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
if (LI == LabelMap.end()) continue;
JumpTarget JT = LI->second;
+ prependAutomaticObjLifetimeWithTerminator(B, I->scopePosition,
+ JT.scopePosition);
prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
JT.scopePosition);
addSuccessor(B, JT.block);
@@ -1209,7 +1252,61 @@ static QualType getReferenceInitTemporaryType(ASTContext &Context,
return Init->getType();
}
-
+
+void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
+ LocalScope::const_iterator E,
+ Stmt *S) {
+ if (BuildOpts.AddImplicitDtors)
+ addAutomaticObjDtors(B, E, S);
+ if (BuildOpts.AddLifetime)
+ addLifetimeEnds(B, E, S);
+}
+
+/// Add to current block automatic objects that leave the scope.
+void CFGBuilder::addLifetimeEnds(LocalScope::const_iterator B,
+ LocalScope::const_iterator E, Stmt *S) {
+ if (!BuildOpts.AddLifetime)
+ return;
+
+ if (B == E)
+ return;
+
+ // To go from B to E, one first goes up the scopes from B to P
+ // then sideways in one scope from P to P' and then down
+ // the scopes from P' to E.
+ // The lifetime of all objects between B and P end.
+ LocalScope::const_iterator P = B.shared_parent(E);
+ int dist = B.distance(P);
+ if (dist <= 0)
+ return;
+
+ // We need to perform the scope leaving in reverse order
+ SmallVector<VarDecl *, 10> DeclsTrivial;
+ SmallVector<VarDecl *, 10> DeclsNonTrivial;
+ DeclsTrivial.reserve(dist);
+ DeclsNonTrivial.reserve(dist);
+
+ for (LocalScope::const_iterator I = B; I != P; ++I)
+ if (hasTrivialDestructor(*I))
+ DeclsTrivial.push_back(*I);
+ else
+ DeclsNonTrivial.push_back(*I);
+
+ autoCreateBlock();
+ // object with trivial destructor end their lifetime last (when storage
+ // duration ends)
+ for (SmallVectorImpl<VarDecl *>::reverse_iterator I = DeclsTrivial.rbegin(),
+ E = DeclsTrivial.rend();
+ I != E; ++I)
+ appendLifetimeEnds(Block, *I, S);
+
+ for (SmallVectorImpl<VarDecl *>::reverse_iterator
+ I = DeclsNonTrivial.rbegin(),
+ E = DeclsNonTrivial.rend();
+ I != E; ++I)
+ appendLifetimeEnds(Block, *I, S);
+}
+
/// addAutomaticObjDtors - Add to current block automatic objects destructors
/// for objects in range of local scope positions. Use S as trigger statement
/// for destructors.
@@ -1309,7 +1406,7 @@ LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
/// that should create implicit scope (e.g. if/else substatements).
void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
- if (!BuildOpts.AddImplicitDtors)
+ if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)
return;
LocalScope *Scope = nullptr;
@@ -1334,7 +1431,7 @@ void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
/// reuse Scope if not NULL.
LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
LocalScope* Scope) {
- if (!BuildOpts.AddImplicitDtors)
+ if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)
return Scope;
for (auto *DI : DS->decls())
@@ -1343,23 +1440,7 @@ LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
return Scope;
}
-/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
-/// create add scope for automatic objects and temporary objects bound to
-/// const reference. Will reuse Scope if not NULL.
-LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
- LocalScope* Scope) {
- if (!BuildOpts.AddImplicitDtors)
- return Scope;
-
- // Check if variable is local.
- switch (VD->getStorageClass()) {
- case SC_None:
- case SC_Auto:
- case SC_Register:
- break;
- default: return Scope;
- }
-
+bool CFGBuilder::hasTrivialDestructor(VarDecl *VD) {
// Check for const references bound to temporary. Set type to pointee.
QualType QT = VD->getType();
if (QT.getTypePtr()->isReferenceType()) {
@@ -1370,44 +1451,74 @@ LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
// temporaries, and a single declaration can extend multiple temporaries.
// We should look at the storage duration on each nested
// MaterializeTemporaryExpr instead.
+
const Expr *Init = VD->getInit();
if (!Init)
- return Scope;
+ return true;
// Lifetime-extending a temporary.
bool FoundMTE = false;
QT = getReferenceInitTemporaryType(*Context, Init, &FoundMTE);
if (!FoundMTE)
- return Scope;
+ return true;
}
// Check for constant size array. Set type to array element type.
while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
if (AT->getSize() == 0)
- return Scope;
+ return true;
QT = AT->getElementType();
}
// Check if type is a C++ class with non-trivial destructor.
if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
- if (CD->hasDefinition() && !CD->hasTrivialDestructor()) {
+ return !CD->hasDefinition() || CD->hasTrivialDestructor();
+ return true;
+}
+
+/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
+/// create add scope for automatic objects and temporary objects bound to
+/// const reference. Will reuse Scope if not NULL.
+LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
+ LocalScope* Scope) {
+ assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
+ "AddImplicitDtors and AddLifetime cannot be used at the same time");
+ if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)
+ return Scope;
+
+ // Check if variable is local.
+ switch (VD->getStorageClass()) {
+ case SC_None:
+ case SC_Auto:
+ case SC_Register:
+ break;
+ default: return Scope;
+ }
+
+ if (BuildOpts.AddImplicitDtors) {
+ if (!hasTrivialDestructor(VD)) {
// Add the variable to scope
Scope = createOrReuseLocalScope(Scope);
Scope->addVar(VD);
ScopePos = Scope->begin();
}
+ return Scope;
+ }
+
+ assert(BuildOpts.AddLifetime);
+ // Add the variable to scope
+ Scope = createOrReuseLocalScope(Scope);
+ Scope->addVar(VD);
+ ScopePos = Scope->begin();
return Scope;
}
/// addLocalScopeAndDtors - For given statement add local scope for it and
/// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
- if (!BuildOpts.AddImplicitDtors)
- return;
-
LocalScope::const_iterator scopeBeginPos = ScopePos;
addLocalScopeForStmt(S);
- addAutomaticObjDtors(ScopePos, scopeBeginPos, S);
+ addAutomaticObjHandling(ScopePos, scopeBeginPos, S);
}
/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
@@ -1419,6 +1530,8 @@ void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
/// no-return destructors properly.
void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
LocalScope::const_iterator B, LocalScope::const_iterator E) {
+ if (!BuildOpts.AddImplicitDtors)
+ return;
BumpVectorContext &C = cfg->getBumpVectorContext();
CFGBlock::iterator InsertPos
= Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
@@ -1427,6 +1540,21 @@ void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
Blk->getTerminator());
}
+/// prependAutomaticObjLifetimeWithTerminator - Prepend lifetime CFGElements for
+/// variables with automatic storage duration to CFGBlock's elements vector.
+/// Elements will be prepended to physical beginning of the vector which
+/// happens to be logical end. Use blocks terminator as statement that specifies
+/// where lifetime ends.
+void CFGBuilder::prependAutomaticObjLifetimeWithTerminator(
+ CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
+ if (!BuildOpts.AddLifetime)
+ return;
+ BumpVectorContext &C = cfg->getBumpVectorContext();
+ CFGBlock::iterator InsertPos =
+ Blk->beginLifetimeEndsInsert(Blk->end(), B.distance(E), C);
+ for (LocalScope::const_iterator I = B; I != E; ++I)
+ InsertPos = Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminator());
+}
/// Visit - Walk the subtree of a statement and add extra
/// blocks for ternary operators, &&, and ||. We also process "," and
/// DeclStmts (which may contain nested control-flow).
@@ -1815,7 +1943,7 @@ CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
// If there is no target for the break, then we are looking at an incomplete
// AST. This means that the CFG cannot be constructed.
if (BreakJumpTarget.block) {
- addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B);
+ addAutomaticObjHandling(ScopePos, BreakJumpTarget.scopePosition, B);
addSuccessor(Block, BreakJumpTarget.block);
} else
badCFG = true;
@@ -1947,13 +2075,12 @@ CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) {
LocalScope::const_iterator scopeBeginPos = ScopePos;
- if (BuildOpts.AddImplicitDtors) {
- addLocalScopeForStmt(C);
- }
+ addLocalScopeForStmt(C);
+
if (!C->body_empty() && !isa<ReturnStmt>(*C->body_rbegin())) {
// If the body ends with a ReturnStmt, the dtors will be added in
// VisitReturnStmt.
- addAutomaticObjDtors(ScopePos, scopeBeginPos, C);
+ addAutomaticObjHandling(ScopePos, scopeBeginPos, C);
}
CFGBlock *LastBlock = Block;
@@ -2183,7 +2310,7 @@ CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
if (VarDecl *VD = I->getConditionVariable())
addLocalScopeForVarDecl(VD);
- addAutomaticObjDtors(ScopePos, save_scope_pos.get(), I);
+ addAutomaticObjHandling(ScopePos, save_scope_pos.get(), I);
// The block we were processing is now finished. Make it the successor
// block.
@@ -2308,7 +2435,7 @@ CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) {
// Create the new block.
Block = createBlock(false);
- addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R);
+ addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), R);
// If the one of the destructors does not return, we already have the Exit
// block as a successor.
@@ -2389,7 +2516,7 @@ CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
else {
JumpTarget JT = I->second;
- addAutomaticObjDtors(ScopePos, JT.scopePosition, G);
+ addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
addSuccessor(Block, JT.block);
}
@@ -2414,7 +2541,7 @@ CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
addLocalScopeForVarDecl(VD);
LocalScope::const_iterator ContinueScopePos = ScopePos;
- addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F);
+ addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);
// "for" is a control-flow statement. Thus we stop processing the current
// block.
@@ -2466,7 +2593,7 @@ CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
ContinueJumpTarget.block->setLoopTarget(F);
// Loop body should end with destructor of Condition variable (if any).
- addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F);
+ addAutomaticObjHandling(ScopePos, LoopBeginScopePos, F);
// If body is not a compound statement create implicit scope
// and add destructors.
@@ -2753,7 +2880,7 @@ CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
LocalScope::const_iterator LoopBeginScopePos = ScopePos;
if (VarDecl *VD = W->getConditionVariable()) {
addLocalScopeForVarDecl(VD);
- addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
+ addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
}
// "while" is a control-flow statement. Thus we stop processing the current
@@ -2788,7 +2915,7 @@ CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
// Loop body should end with destructor of Condition variable (if any).
- addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
+ addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
// If body is not a compound statement create implicit scope
// and add destructors.
@@ -3030,7 +3157,7 @@ CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
// If there is no target for the continue, then we are looking at an
// incomplete AST. This means the CFG cannot be constructed.
if (ContinueJumpTarget.block) {
- addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C);
+ addAutomaticObjHandling(ScopePos, ContinueJumpTarget.scopePosition, C);
addSuccessor(Block, ContinueJumpTarget.block);
} else
badCFG = true;
@@ -3085,7 +3212,7 @@ CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
if (VarDecl *VD = Terminator->getConditionVariable())
addLocalScopeForVarDecl(VD);
- addAutomaticObjDtors(ScopePos, save_scope_pos.get(), Terminator);
+ addAutomaticObjHandling(ScopePos, save_scope_pos.get(), Terminator);
if (Block) {
if (badCFG)
@@ -3373,7 +3500,7 @@ CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
if (VarDecl *VD = CS->getExceptionDecl()) {
LocalScope::const_iterator BeginScopePos = ScopePos;
addLocalScopeForVarDecl(VD);
- addAutomaticObjDtors(ScopePos, BeginScopePos, CS);
+ addAutomaticObjHandling(ScopePos, BeginScopePos, CS);
}
if (CS->getHandlerBlock())
@@ -3427,7 +3554,7 @@ CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
addLocalScopeForStmt(Begin);
if (Stmt *End = S->getEndStmt())
addLocalScopeForStmt(End);
- addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S);
+ addAutomaticObjHandling(ScopePos, save_scope_pos.get(), S);
LocalScope::const_iterator ContinueScopePos = ScopePos;
@@ -3898,6 +4025,7 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
case CFGElement::Statement:
case CFGElement::Initializer:
case CFGElement::NewAllocator:
+ case CFGElement::LifetimeEnds:
llvm_unreachable("getDestructorDecl should only be used with "
"ImplicitDtors");
case CFGElement::AutomaticObjectDtor: {
@@ -4308,6 +4436,12 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
OS << " (Implicit destructor)\n";
+ } else if (Optional<CFGLifetimeEnds> DE = E.getAs<CFGLifetimeEnds>()) {
+ const VarDecl *VD = DE->getVarDecl();
+ Helper.handleDecl(VD, OS);
+
+ OS << " (Lifetime ends)\n";
+
} else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) {
OS << "CFGNewAllocator(";
if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr())
diff --git a/lib/Analysis/CloneDetection.cpp b/lib/Analysis/CloneDetection.cpp
index ee848ac711d6a..5ea74989a7ec9 100644
--- a/lib/Analysis/CloneDetection.cpp
+++ b/lib/Analysis/CloneDetection.cpp
@@ -16,13 +16,13 @@
#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/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)
@@ -103,12 +103,8 @@ static void printMacroName(llvm::raw_string_ostream &MacroStack,
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.
-static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
+std::string clone_detection::getMacroStack(SourceLocation Loc,
+ ASTContext &Context) {
std::string MacroStack;
llvm::raw_string_ostream MacroStackStream(MacroStack);
SourceManager &SM = Context.getSourceManager();
@@ -123,184 +119,6 @@ static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
return MacroStack;
}
-namespace {
-typedef unsigned DataPiece;
-
-/// 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;
- /// 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);
- }
-
- // Below are utility methods for appending different data to the vector.
-
- void addData(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<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
-
void CloneDetector::analyzeCodeBody(const Decl *D) {
assert(D);
assert(D->hasBody());
@@ -421,16 +239,27 @@ size_t RecursiveCloneTypeIIConstraint::saveHash(
}
if (CS) {
- for (unsigned Length = 2; Length <= CS->size(); ++Length) {
- for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
- llvm::MD5 Hash;
- for (unsigned i = Pos; i < Pos + Length; ++i) {
- size_t ChildHash = ChildHashes[i];
- Hash.update(StringRef(reinterpret_cast<char *>(&ChildHash),
- sizeof(ChildHash)));
+ // If we're in a CompoundStmt, we hash all possible combinations of child
+ // statements to find clones in those subsequences.
+ // We first go through every possible starting position of a subsequence.
+ for (unsigned Pos = 0; Pos < CS->size(); ++Pos) {
+ // Then we try all possible lengths this subsequence could have and
+ // reuse the same hash object to make sure we only hash every child
+ // hash exactly once.
+ llvm::MD5 Hash;
+ for (unsigned Length = 1; Length <= CS->size() - Pos; ++Length) {
+ // Grab the current child hash and put it into our hash. We do
+ // -1 on the index because we start counting the length at 1.
+ size_t ChildHash = ChildHashes[Pos + Length - 1];
+ Hash.update(
+ StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));
+ // If we have at least two elements in our subsequence, we can start
+ // saving it.
+ if (Length > 1) {
+ llvm::MD5 SubHash = Hash;
+ StmtsByHash.push_back(std::make_pair(
+ createHash(SubHash), StmtSequence(CS, D, Pos, Pos + Length)));
}
- StmtsByHash.push_back(std::make_pair(
- createHash(Hash), StmtSequence(CS, D, Pos, Pos + Length)));
}
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-02 01:14:40 +0000