/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/CloneDetection.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | /// |
9 | | /// This file implements classes for searching and analyzing source code clones. |
10 | | /// |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "clang/Analysis/CloneDetection.h" |
14 | | #include "clang/AST/Attr.h" |
15 | | #include "clang/AST/DataCollection.h" |
16 | | #include "clang/AST/DeclTemplate.h" |
17 | | #include "clang/Basic/SourceManager.h" |
18 | | #include "llvm/Support/MD5.h" |
19 | | #include "llvm/Support/Path.h" |
20 | | |
21 | | using namespace clang; |
22 | | |
23 | | StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D, |
24 | | unsigned StartIndex, unsigned EndIndex) |
25 | 276 | : S(Stmt), D(D), StartIndex(StartIndex), EndIndex(EndIndex) { |
26 | 276 | assert(Stmt && "Stmt must not be a nullptr"); |
27 | 0 | assert(StartIndex < EndIndex && "Given array should not be empty"); |
28 | 0 | assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt"); |
29 | 276 | } |
30 | | |
31 | | StmtSequence::StmtSequence(const Stmt *Stmt, const Decl *D) |
32 | 10.8k | : S(Stmt), D(D), StartIndex(0), EndIndex(0) {} |
33 | | |
34 | | StmtSequence::StmtSequence() |
35 | 0 | : S(nullptr), D(nullptr), StartIndex(0), EndIndex(0) {} |
36 | | |
37 | 1.46k | bool StmtSequence::contains(const StmtSequence &Other) const { |
38 | | // If both sequences reside in different declarations, they can never contain |
39 | | // each other. |
40 | 1.46k | if (D != Other.D) |
41 | 1.05k | return false; |
42 | | |
43 | 410 | const SourceManager &SM = getASTContext().getSourceManager(); |
44 | | |
45 | | // Otherwise check if the start and end locations of the current sequence |
46 | | // surround the other sequence. |
47 | 410 | bool StartIsInBounds = |
48 | 410 | SM.isBeforeInTranslationUnit(getBeginLoc(), Other.getBeginLoc()) || |
49 | 410 | getBeginLoc() == Other.getBeginLoc()209 ; |
50 | 410 | if (!StartIsInBounds) |
51 | 158 | return false; |
52 | | |
53 | 252 | bool EndIsInBounds = |
54 | 252 | SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) || |
55 | 252 | Other.getEndLoc() == getEndLoc()96 ; |
56 | 252 | return EndIsInBounds; |
57 | 410 | } |
58 | | |
59 | 15.3k | StmtSequence::iterator StmtSequence::begin() const { |
60 | 15.3k | if (!holdsSequence()) { |
61 | 13.6k | return &S; |
62 | 13.6k | } |
63 | 1.63k | auto CS = cast<CompoundStmt>(S); |
64 | 1.63k | return CS->body_begin() + StartIndex; |
65 | 15.3k | } |
66 | | |
67 | 6.45k | StmtSequence::iterator StmtSequence::end() const { |
68 | 6.45k | if (!holdsSequence()) { |
69 | 6.19k | return reinterpret_cast<StmtSequence::iterator>(&S) + 1; |
70 | 6.19k | } |
71 | 262 | auto CS = cast<CompoundStmt>(S); |
72 | 262 | return CS->body_begin() + EndIndex; |
73 | 6.45k | } |
74 | | |
75 | 10.5k | ASTContext &StmtSequence::getASTContext() const { |
76 | 10.5k | assert(D); |
77 | 0 | return D->getASTContext(); |
78 | 10.5k | } |
79 | | |
80 | 4.67k | SourceLocation StmtSequence::getBeginLoc() const { |
81 | 4.67k | return front()->getBeginLoc(); |
82 | 4.67k | } |
83 | | |
84 | 729 | SourceLocation StmtSequence::getEndLoc() const { return back()->getEndLoc(); } |
85 | | |
86 | 33 | SourceRange StmtSequence::getSourceRange() const { |
87 | 33 | return SourceRange(getBeginLoc(), getEndLoc()); |
88 | 33 | } |
89 | | |
90 | 97 | void CloneDetector::analyzeCodeBody(const Decl *D) { |
91 | 97 | assert(D); |
92 | 0 | assert(D->hasBody()); |
93 | | |
94 | 0 | Sequences.push_back(StmtSequence(D->getBody(), D)); |
95 | 97 | } |
96 | | |
97 | | /// Returns true if and only if \p Stmt contains at least one other |
98 | | /// sequence in the \p Group. |
99 | | static bool containsAnyInGroup(StmtSequence &Seq, |
100 | 680 | CloneDetector::CloneGroup &Group) { |
101 | 1.46k | for (StmtSequence &GroupSeq : Group) { |
102 | 1.46k | if (Seq.contains(GroupSeq)) |
103 | 201 | return true; |
104 | 1.46k | } |
105 | 479 | return false; |
106 | 680 | } |
107 | | |
108 | | /// Returns true if and only if all sequences in \p OtherGroup are |
109 | | /// contained by a sequence in \p Group. |
110 | | static bool containsGroup(CloneDetector::CloneGroup &Group, |
111 | 600 | CloneDetector::CloneGroup &OtherGroup) { |
112 | | // We have less sequences in the current group than we have in the other, |
113 | | // so we will never fulfill the requirement for returning true. This is only |
114 | | // possible because we know that a sequence in Group can contain at most |
115 | | // one sequence in OtherGroup. |
116 | 600 | if (Group.size() < OtherGroup.size()) |
117 | 42 | return false; |
118 | | |
119 | 680 | for (StmtSequence &Stmt : Group)558 { |
120 | 680 | if (!containsAnyInGroup(Stmt, OtherGroup)) |
121 | 479 | return false; |
122 | 680 | } |
123 | 79 | return true; |
124 | 558 | } |
125 | | |
126 | | void OnlyLargestCloneConstraint::constrain( |
127 | 30 | std::vector<CloneDetector::CloneGroup> &Result) { |
128 | 30 | std::vector<unsigned> IndexesToRemove; |
129 | | |
130 | | // Compare every group in the result with the rest. If one groups contains |
131 | | // another group, we only need to return the bigger group. |
132 | | // Note: This doesn't scale well, so if possible avoid calling any heavy |
133 | | // function from this loop to minimize the performance impact. |
134 | 132 | for (unsigned i = 0; i < Result.size(); ++i102 ) { |
135 | 664 | for (unsigned j = 0; j < Result.size(); ++j562 ) { |
136 | | // Don't compare a group with itself. |
137 | 641 | if (i == j) |
138 | 41 | continue; |
139 | | |
140 | 600 | if (containsGroup(Result[j], Result[i])) { |
141 | 79 | IndexesToRemove.push_back(i); |
142 | 79 | break; |
143 | 79 | } |
144 | 600 | } |
145 | 102 | } |
146 | | |
147 | | // Erasing a list of indexes from the vector should be done with decreasing |
148 | | // indexes. As IndexesToRemove is constructed with increasing values, we just |
149 | | // reverse iterate over it to get the desired order. |
150 | 30 | for (unsigned I : llvm::reverse(IndexesToRemove)) |
151 | 79 | Result.erase(Result.begin() + I); |
152 | 30 | } |
153 | | |
154 | | bool FilenamePatternConstraint::isAutoGenerated( |
155 | 28 | const CloneDetector::CloneGroup &Group) { |
156 | 28 | if (IgnoredFilesPattern.empty() || Group.empty() || |
157 | 28 | !IgnoredFilesRegex->isValid()27 ) |
158 | 1 | return false; |
159 | | |
160 | 93 | for (const StmtSequence &S : Group)27 { |
161 | 93 | const SourceManager &SM = S.getASTContext().getSourceManager(); |
162 | 93 | StringRef Filename = llvm::sys::path::filename( |
163 | 93 | SM.getFilename(S.getContainingDecl()->getLocation())); |
164 | 93 | if (IgnoredFilesRegex->match(Filename)) |
165 | 4 | return true; |
166 | 93 | } |
167 | | |
168 | 23 | return false; |
169 | 27 | } |
170 | | |
171 | | /// This class defines what a type II code clone is: If it collects for two |
172 | | /// statements the same data, then those two statements are considered to be |
173 | | /// clones of each other. |
174 | | /// |
175 | | /// All collected data is forwarded to the given data consumer of the type T. |
176 | | /// The data consumer class needs to provide a member method with the signature: |
177 | | /// update(StringRef Str) |
178 | | namespace { |
179 | | template <class T> |
180 | | class CloneTypeIIStmtDataCollector |
181 | | : public ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>> { |
182 | | ASTContext &Context; |
183 | | /// The data sink to which all data is forwarded. |
184 | | T &DataConsumer; |
185 | | |
186 | 35.4k | template <class Ty> void addData(const Ty &Data) { |
187 | 35.4k | data_collection::addDataToConsumer(DataConsumer, Data); |
188 | 35.4k | } CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<bool>(bool const&) Line | Count | Source | 186 | 31 | template <class Ty> void addData(const Ty &Data) { | 187 | 31 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 31 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) Line | Count | Source | 186 | 3.59k | template <class Ty> void addData(const Ty &Data) { | 187 | 3.59k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 3.59k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<llvm::StringRef>(llvm::StringRef const&) Line | Count | Source | 186 | 22 | template <class Ty> void addData(const Ty &Data) { | 187 | 22 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 22 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::Stmt::StmtClass>(clang::Stmt::StmtClass const&) Line | Count | Source | 186 | 1.77k | template <class Ty> void addData(const Ty &Data) { | 187 | 1.77k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 1.77k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::QualType>(clang::QualType const&) Line | Count | Source | 186 | 1.40k | template <class Ty> void addData(const Ty &Data) { | 187 | 1.40k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 1.40k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<unsigned int>(unsigned int const&) Line | Count | Source | 186 | 20 | template <class Ty> void addData(const Ty &Data) { | 187 | 20 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 20 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::ArrayTypeTrait>(clang::ArrayTypeTrait const&) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::BinaryOperatorKind>(clang::BinaryOperatorKind const&) Line | Count | Source | 186 | 273 | template <class Ty> void addData(const Ty &Data) { | 187 | 273 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 273 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::ObjCBridgeCastKind>(clang::ObjCBridgeCastKind const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::ExpressionTrait>(clang::ExpressionTrait const&) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::LambdaCaptureKind>(clang::LambdaCaptureKind const&) Line | Count | Source | 186 | 5 | template <class Ty> void addData(const Ty &Data) { | 187 | 5 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 5 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::PredefinedExpr::IdentKind>(clang::PredefinedExpr::IdentKind const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::TypeTrait>(clang::TypeTrait const&) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::UnaryOperatorKind>(clang::UnaryOperatorKind const&) Line | Count | Source | 186 | 45 | template <class Ty> void addData(const Ty &Data) { | 187 | 45 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 45 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<bool>(bool const&) Line | Count | Source | 186 | 4 | template <class Ty> void addData(const Ty &Data) { | 187 | 4 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 4 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) Line | Count | Source | 186 | 13.3k | template <class Ty> void addData(const Ty &Data) { | 187 | 13.3k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 13.3k | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<llvm::StringRef>(llvm::StringRef const&) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::Stmt::StmtClass>(clang::Stmt::StmtClass const&) Line | Count | Source | 186 | 6.61k | template <class Ty> void addData(const Ty &Data) { | 187 | 6.61k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 6.61k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::QualType>(clang::QualType const&) Line | Count | Source | 186 | 6.22k | template <class Ty> void addData(const Ty &Data) { | 187 | 6.22k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 6.22k | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<unsigned int>(unsigned int const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::ArrayTypeTrait>(clang::ArrayTypeTrait const&) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::BinaryOperatorKind>(clang::BinaryOperatorKind const&) Line | Count | Source | 186 | 2.01k | template <class Ty> void addData(const Ty &Data) { | 187 | 2.01k | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 2.01k | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::ObjCBridgeCastKind>(clang::ObjCBridgeCastKind const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::ExpressionTrait>(clang::ExpressionTrait const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::LambdaCaptureKind>(clang::LambdaCaptureKind const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::PredefinedExpr::IdentKind>(clang::PredefinedExpr::IdentKind const&) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::TypeTrait>(clang::TypeTrait const&) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::addData<clang::UnaryOperatorKind>(clang::UnaryOperatorKind const&) Line | Count | Source | 186 | 118 | template <class Ty> void addData(const Ty &Data) { | 187 | 118 | data_collection::addDataToConsumer(DataConsumer, Data); | 188 | 118 | } |
|
189 | | |
190 | | public: |
191 | | CloneTypeIIStmtDataCollector(const Stmt *S, ASTContext &Context, |
192 | | T &DataConsumer) |
193 | 8.39k | : Context(Context), DataConsumer(DataConsumer) { |
194 | 8.39k | this->Visit(S); |
195 | 8.39k | } CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::CloneTypeIIStmtDataCollector(clang::Stmt const*, clang::ASTContext&, llvm::MD5&) Line | Count | Source | 193 | 1.77k | : Context(Context), DataConsumer(DataConsumer) { | 194 | 1.77k | this->Visit(S); | 195 | 1.77k | } |
CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::CloneTypeIIStmtDataCollector(clang::Stmt const*, clang::ASTContext&, (anonymous namespace)::FoldingSetNodeIDWrapper&) Line | Count | Source | 193 | 6.61k | : Context(Context), DataConsumer(DataConsumer) { | 194 | 6.61k | this->Visit(S); | 195 | 6.61k | } |
|
196 | | |
197 | | // Define a visit method for each class to collect data and subsequently visit |
198 | | // all parent classes. This uses a template so that custom visit methods by us |
199 | | // take precedence. |
200 | | #define DEF_ADD_DATA(CLASS, CODE) \ |
201 | 18.5k | template <class = void> void Visit##CLASS(const CLASS *S) { \ |
202 | 18.5k | CODE449 ; \ |
203 | 18.5k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ |
204 | 18.5k | } CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitAsmStmt<void>(clang::AsmStmt const*) Line | Count | Source | 201 | 3 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 27 | CODE; \ | 203 | 3 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 3 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitStmt<void>(clang::Stmt const*) Line | Count | Source | 201 | 1.77k | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 1.77k | CODE; \ | 203 | 1.77k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 1.77k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitCXXCatchStmt<void>(clang::CXXCatchStmt const*) Line | Count | Source | 201 | 5 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 5 | CODE; \ | 203 | 5 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 5 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitDeclStmt<void>(clang::DeclStmt const*) Line | Count | Source | 201 | 20 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 60 | CODE; \ | 203 | 20 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 20 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitGotoStmt<void>(clang::GotoStmt const*) Line | Count | Source | 201 | 4 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 4 | CODE; \ | 203 | 4 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 4 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitIndirectGotoStmt<void>(clang::IndirectGotoStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitMSDependentExistsStmt<void>(clang::MSDependentExistsStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitObjCAtCatchStmt<void>(clang::ObjCAtCatchStmt const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitAttributedStmt<void>(clang::AttributedStmt const*) Line | Count | Source | 201 | 1 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 1 | CODE; \ | 203 | 1 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 1 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitExpr<void>(clang::Expr const*) Line | Count | Source | 201 | 1.37k | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 1.37k | CODE; \ | 203 | 1.37k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 1.37k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitAddrLabelExpr<void>(clang::AddrLabelExpr const*) Line | Count | Source | 201 | 4 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 4 | CODE; \ | 203 | 4 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 4 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitArrayTypeTraitExpr<void>(clang::ArrayTypeTraitExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitBinaryOperator<void>(clang::BinaryOperator const*) Line | Count | Source | 201 | 273 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 273 | CODE; \ | 203 | 273 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 273 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitCXXDeleteExpr<void>(clang::CXXDeleteExpr const*) Line | Count | Source | 201 | 5 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 5 | CODE; \ | 203 | 5 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 5 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitCXXFoldExpr<void>(clang::CXXFoldExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitCallExpr<void>(clang::CallExpr const*) Line | Count | Source | 201 | 32 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 134 | CODE; \ | 203 | 32 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 32 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitObjCBridgedCastExpr<void>(clang::ObjCBridgedCastExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitExpressionTraitExpr<void>(clang::ExpressionTraitExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitGenericSelectionExpr<void>(clang::GenericSelectionExpr const*) Line | Count | Source | 201 | 3 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 8 | CODE; \ | 203 | 3 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 3 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitLambdaExpr<void>(clang::LambdaExpr const*) Line | Count | Source | 201 | 5 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 15 | CODE; \ | 203 | 5 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 5 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitObjCIndirectCopyRestoreExpr<void>(clang::ObjCIndirectCopyRestoreExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitObjCPropertyRefExpr<void>(clang::ObjCPropertyRefExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitPredefinedExpr<void>(clang::PredefinedExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitTypeTraitExpr<void>(clang::TypeTraitExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitUnaryOperator<void>(clang::UnaryOperator const*) Line | Count | Source | 201 | 45 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 45 | CODE; \ | 203 | 45 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 45 | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitLabelStmt<void>(clang::LabelStmt const*) Line | Count | Source | 201 | 8 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 8 | CODE; \ | 203 | 8 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 8 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitAsmStmt<void>(clang::AsmStmt const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitStmt<void>(clang::Stmt const*) Line | Count | Source | 201 | 6.61k | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 6.61k | CODE; \ | 203 | 6.61k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 6.61k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitCXXCatchStmt<void>(clang::CXXCatchStmt const*) Line | Count | Source | 201 | 2 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 2 | CODE; \ | 203 | 2 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 2 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitDeclStmt<void>(clang::DeclStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitGotoStmt<void>(clang::GotoStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitIndirectGotoStmt<void>(clang::IndirectGotoStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitMSDependentExistsStmt<void>(clang::MSDependentExistsStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitObjCAtCatchStmt<void>(clang::ObjCAtCatchStmt const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitAttributedStmt<void>(clang::AttributedStmt const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitExpr<void>(clang::Expr const*) Line | Count | Source | 201 | 6.22k | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 6.22k | CODE; \ | 203 | 6.22k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 6.22k | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitAddrLabelExpr<void>(clang::AddrLabelExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitArrayTypeTraitExpr<void>(clang::ArrayTypeTraitExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitBinaryOperator<void>(clang::BinaryOperator const*) Line | Count | Source | 201 | 2.01k | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 2.01k | CODE; \ | 203 | 2.01k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 2.01k | } |
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitCXXDeleteExpr<void>(clang::CXXDeleteExpr const*) Line | Count | Source | 201 | 2 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 2 | CODE; \ | 203 | 2 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 2 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitCXXFoldExpr<void>(clang::CXXFoldExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitCallExpr<void>(clang::CallExpr const*) Line | Count | Source | 201 | 68 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 204 | CODE; \ | 203 | 68 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 68 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitObjCBridgedCastExpr<void>(clang::ObjCBridgedCastExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitExpressionTraitExpr<void>(clang::ExpressionTraitExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitGenericSelectionExpr<void>(clang::GenericSelectionExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitLambdaExpr<void>(clang::LambdaExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitObjCIndirectCopyRestoreExpr<void>(clang::ObjCIndirectCopyRestoreExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitObjCPropertyRefExpr<void>(clang::ObjCPropertyRefExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitPredefinedExpr<void>(clang::PredefinedExpr const*) Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitTypeTraitExpr<void>(clang::TypeTraitExpr const*) CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitUnaryOperator<void>(clang::UnaryOperator const*) Line | Count | Source | 201 | 118 | template <class = void> void Visit##CLASS(const CLASS *S) { \ | 202 | 118 | CODE; \ | 203 | 118 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 204 | 118 | } |
Unexecuted instantiation: CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitLabelStmt<void>(clang::LabelStmt const*) |
205 | | |
206 | | #include "clang/AST/StmtDataCollectors.inc" |
207 | | |
208 | | // Type II clones ignore variable names and literals, so let's skip them. |
209 | | #define SKIP(CLASS) \ |
210 | 3.54k | void Visit##CLASS(const CLASS *S) { \ |
211 | 3.54k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ |
212 | 3.54k | } CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitCXXBoolLiteralExpr(clang::CXXBoolLiteralExpr const*) Line | Count | Source | 210 | 52 | void Visit##CLASS(const CLASS *S) { \ | 211 | 52 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 52 | } |
Unexecuted instantiation: CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitCharacterLiteral(clang::CharacterLiteral const*) CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitDeclRefExpr(clang::DeclRefExpr const*) Line | Count | Source | 210 | 388 | void Visit##CLASS(const CLASS *S) { \ | 211 | 388 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 388 | } |
Unexecuted instantiation: CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitFloatingLiteral(clang::FloatingLiteral const*) CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitIntegerLiteral(clang::IntegerLiteral const*) Line | Count | Source | 210 | 195 | void Visit##CLASS(const CLASS *S) { \ | 211 | 195 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 195 | } |
CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitMemberExpr(clang::MemberExpr const*) Line | Count | Source | 210 | 5 | void Visit##CLASS(const CLASS *S) { \ | 211 | 5 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 5 | } |
Unexecuted instantiation: CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::VisitStringLiteral(clang::StringLiteral const*) CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitCXXBoolLiteralExpr(clang::CXXBoolLiteralExpr const*) Line | Count | Source | 210 | 14 | void Visit##CLASS(const CLASS *S) { \ | 211 | 14 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 14 | } |
Unexecuted instantiation: CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitCharacterLiteral(clang::CharacterLiteral const*) CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitDeclRefExpr(clang::DeclRefExpr const*) Line | Count | Source | 210 | 1.53k | void Visit##CLASS(const CLASS *S) { \ | 211 | 1.53k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 1.53k | } |
Unexecuted instantiation: CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitFloatingLiteral(clang::FloatingLiteral const*) CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitIntegerLiteral(clang::IntegerLiteral const*) Line | Count | Source | 210 | 1.33k | void Visit##CLASS(const CLASS *S) { \ | 211 | 1.33k | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 1.33k | } |
CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitMemberExpr(clang::MemberExpr const*) Line | Count | Source | 210 | 22 | void Visit##CLASS(const CLASS *S) { \ | 211 | 22 | ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S); \ | 212 | 22 | } |
Unexecuted instantiation: CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<(anonymous namespace)::FoldingSetNodeIDWrapper>::VisitStringLiteral(clang::StringLiteral const*) |
213 | | SKIP(DeclRefExpr) |
214 | | SKIP(MemberExpr) |
215 | | SKIP(IntegerLiteral) |
216 | | SKIP(FloatingLiteral) |
217 | | SKIP(StringLiteral) |
218 | | SKIP(CXXBoolLiteralExpr) |
219 | | SKIP(CharacterLiteral) |
220 | | #undef SKIP |
221 | | }; |
222 | | } // end anonymous namespace |
223 | | |
224 | 2.05k | static size_t createHash(llvm::MD5 &Hash) { |
225 | 2.05k | size_t HashCode; |
226 | | |
227 | | // Create the final hash code for the current Stmt. |
228 | 2.05k | llvm::MD5::MD5Result HashResult; |
229 | 2.05k | Hash.final(HashResult); |
230 | | |
231 | | // Copy as much as possible of the generated hash code to the Stmt's hash |
232 | | // code. |
233 | 2.05k | std::memcpy(&HashCode, &HashResult, |
234 | 2.05k | std::min(sizeof(HashCode), sizeof(HashResult))); |
235 | | |
236 | 2.05k | return HashCode; |
237 | 2.05k | } |
238 | | |
239 | | /// Generates and saves a hash code for the given Stmt. |
240 | | /// \param S The given Stmt. |
241 | | /// \param D The Decl containing S. |
242 | | /// \param StmtsByHash Output parameter that will contain the hash codes for |
243 | | /// each StmtSequence in the given Stmt. |
244 | | /// \return The hash code of the given Stmt. |
245 | | /// |
246 | | /// If the given Stmt is a CompoundStmt, this method will also generate |
247 | | /// hashes for all possible StmtSequences in the children of this Stmt. |
248 | | static size_t |
249 | | saveHash(const Stmt *S, const Decl *D, |
250 | 1.77k | std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) { |
251 | 1.77k | llvm::MD5 Hash; |
252 | 1.77k | ASTContext &Context = D->getASTContext(); |
253 | | |
254 | 1.77k | CloneTypeIIStmtDataCollector<llvm::MD5>(S, Context, Hash); |
255 | | |
256 | 1.77k | auto CS = dyn_cast<CompoundStmt>(S); |
257 | 1.77k | SmallVector<size_t, 8> ChildHashes; |
258 | | |
259 | 1.77k | for (const Stmt *Child : S->children()) { |
260 | 1.68k | if (Child == nullptr) { |
261 | 0 | ChildHashes.push_back(0); |
262 | 0 | continue; |
263 | 0 | } |
264 | 1.68k | size_t ChildHash = saveHash(Child, D, StmtsByHash); |
265 | 1.68k | Hash.update( |
266 | 1.68k | StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash))); |
267 | 1.68k | ChildHashes.push_back(ChildHash); |
268 | 1.68k | } |
269 | | |
270 | 1.77k | if (CS) { |
271 | | // If we're in a CompoundStmt, we hash all possible combinations of child |
272 | | // statements to find clones in those subsequences. |
273 | | // We first go through every possible starting position of a subsequence. |
274 | 408 | for (unsigned Pos = 0; Pos < CS->size(); ++Pos271 ) { |
275 | | // Then we try all possible lengths this subsequence could have and |
276 | | // reuse the same hash object to make sure we only hash every child |
277 | | // hash exactly once. |
278 | 271 | llvm::MD5 Hash; |
279 | 818 | for (unsigned Length = 1; Length <= CS->size() - Pos; ++Length547 ) { |
280 | | // Grab the current child hash and put it into our hash. We do |
281 | | // -1 on the index because we start counting the length at 1. |
282 | 547 | size_t ChildHash = ChildHashes[Pos + Length - 1]; |
283 | 547 | Hash.update( |
284 | 547 | StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash))); |
285 | | // If we have at least two elements in our subsequence, we can start |
286 | | // saving it. |
287 | 547 | if (Length > 1) { |
288 | 276 | llvm::MD5 SubHash = Hash; |
289 | 276 | StmtsByHash.push_back(std::make_pair( |
290 | 276 | createHash(SubHash), StmtSequence(CS, D, Pos, Pos + Length))); |
291 | 276 | } |
292 | 547 | } |
293 | 271 | } |
294 | 137 | } |
295 | | |
296 | 1.77k | size_t HashCode = createHash(Hash); |
297 | 1.77k | StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D))); |
298 | 1.77k | return HashCode; |
299 | 1.77k | } |
300 | | |
301 | | namespace { |
302 | | /// Wrapper around FoldingSetNodeID that it can be used as the template |
303 | | /// argument of the StmtDataCollector. |
304 | | class FoldingSetNodeIDWrapper { |
305 | | |
306 | | llvm::FoldingSetNodeID &FS; |
307 | | |
308 | | public: |
309 | 300 | FoldingSetNodeIDWrapper(llvm::FoldingSetNodeID &FS) : FS(FS) {} |
310 | | |
311 | 28.2k | void update(StringRef Str) { FS.AddString(Str); } |
312 | | }; |
313 | | } // end anonymous namespace |
314 | | |
315 | | /// Writes the relevant data from all statements and child statements |
316 | | /// in the given StmtSequence into the given FoldingSetNodeID. |
317 | | static void CollectStmtSequenceData(const StmtSequence &Sequence, |
318 | 6.26k | FoldingSetNodeIDWrapper &OutputData) { |
319 | 6.61k | for (const Stmt *S : Sequence) { |
320 | 6.61k | CloneTypeIIStmtDataCollector<FoldingSetNodeIDWrapper>( |
321 | 6.61k | S, Sequence.getASTContext(), OutputData); |
322 | | |
323 | 6.61k | for (const Stmt *Child : S->children()) { |
324 | 5.96k | if (!Child) |
325 | 0 | continue; |
326 | | |
327 | 5.96k | CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()), |
328 | 5.96k | OutputData); |
329 | 5.96k | } |
330 | 6.61k | } |
331 | 6.26k | } |
332 | | |
333 | | /// Returns true if both sequences are clones of each other. |
334 | | static bool areSequencesClones(const StmtSequence &LHS, |
335 | 150 | const StmtSequence &RHS) { |
336 | | // We collect the data from all statements in the sequence as we did before |
337 | | // when generating a hash value for each sequence. But this time we don't |
338 | | // hash the collected data and compare the whole data set instead. This |
339 | | // prevents any false-positives due to hash code collisions. |
340 | 150 | llvm::FoldingSetNodeID DataLHS, DataRHS; |
341 | 150 | FoldingSetNodeIDWrapper LHSWrapper(DataLHS); |
342 | 150 | FoldingSetNodeIDWrapper RHSWrapper(DataRHS); |
343 | | |
344 | 150 | CollectStmtSequenceData(LHS, LHSWrapper); |
345 | 150 | CollectStmtSequenceData(RHS, RHSWrapper); |
346 | | |
347 | 150 | return DataLHS == DataRHS; |
348 | 150 | } |
349 | | |
350 | | void RecursiveCloneTypeIIHashConstraint::constrain( |
351 | 30 | std::vector<CloneDetector::CloneGroup> &Sequences) { |
352 | | // FIXME: Maybe we can do this in-place and don't need this additional vector. |
353 | 30 | std::vector<CloneDetector::CloneGroup> Result; |
354 | | |
355 | 30 | for (CloneDetector::CloneGroup &Group : Sequences) { |
356 | | // We assume in the following code that the Group is non-empty, so we |
357 | | // skip all empty groups. |
358 | 28 | if (Group.empty()) |
359 | 1 | continue; |
360 | | |
361 | 27 | std::vector<std::pair<size_t, StmtSequence>> StmtsByHash; |
362 | | |
363 | | // Generate hash codes for all children of S and save them in StmtsByHash. |
364 | 97 | for (const StmtSequence &S : Group) { |
365 | 97 | saveHash(S.front(), S.getContainingDecl(), StmtsByHash); |
366 | 97 | } |
367 | | |
368 | | // Sort hash_codes in StmtsByHash. |
369 | 27 | llvm::stable_sort(StmtsByHash, llvm::less_first()); |
370 | | |
371 | | // Check for each StmtSequence if its successor has the same hash value. |
372 | | // We don't check the last StmtSequence as it has no successor. |
373 | | // Note: The 'size - 1 ' in the condition is safe because we check for an |
374 | | // empty Group vector at the beginning of this function. |
375 | 717 | for (unsigned i = 0; i < StmtsByHash.size() - 1; ++i690 ) { |
376 | 690 | const auto Current = StmtsByHash[i]; |
377 | | |
378 | | // It's likely that we just found a sequence of StmtSequences that |
379 | | // represent a CloneGroup, so we create a new group and start checking and |
380 | | // adding the StmtSequences in this sequence. |
381 | 690 | CloneDetector::CloneGroup NewGroup; |
382 | | |
383 | 690 | size_t PrototypeHash = Current.first; |
384 | | |
385 | 2.73k | for (; i < StmtsByHash.size(); ++i2.04k ) { |
386 | | // A different hash value means we have reached the end of the sequence. |
387 | 2.71k | if (PrototypeHash != StmtsByHash[i].first) { |
388 | | // The current sequence could be the start of a new CloneGroup. So we |
389 | | // decrement i so that we visit it again in the outer loop. |
390 | | // Note: i can never be 0 at this point because we are just comparing |
391 | | // the hash of the Current StmtSequence with itself in the 'if' above. |
392 | 674 | assert(i != 0); |
393 | 0 | --i; |
394 | 674 | break; |
395 | 674 | } |
396 | | // Same hash value means we should add the StmtSequence to the current |
397 | | // group. |
398 | 2.04k | NewGroup.push_back(StmtsByHash[i].second); |
399 | 2.04k | } |
400 | | |
401 | | // We created a new clone group with matching hash codes and move it to |
402 | | // the result vector. |
403 | 690 | Result.push_back(NewGroup); |
404 | 690 | } |
405 | 27 | } |
406 | | // Sequences is the output parameter, so we copy our result into it. |
407 | 30 | Sequences = Result; |
408 | 30 | } |
409 | | |
410 | | void RecursiveCloneTypeIIVerifyConstraint::constrain( |
411 | 30 | std::vector<CloneDetector::CloneGroup> &Sequences) { |
412 | 30 | CloneConstraint::splitCloneGroups( |
413 | 150 | Sequences, [](const StmtSequence &A, const StmtSequence &B) { |
414 | 150 | return areSequencesClones(A, B); |
415 | 150 | }); |
416 | 30 | } |
417 | | |
418 | | size_t MinComplexityConstraint::calculateStmtComplexity( |
419 | | const StmtSequence &Seq, std::size_t Limit, |
420 | 3.40k | const std::string &ParentMacroStack) { |
421 | 3.40k | if (Seq.empty()) |
422 | 0 | return 0; |
423 | | |
424 | 3.40k | size_t Complexity = 1; |
425 | | |
426 | 3.40k | ASTContext &Context = Seq.getASTContext(); |
427 | | |
428 | | // Look up what macros expanded into the current statement. |
429 | 3.40k | std::string MacroStack = |
430 | 3.40k | data_collection::getMacroStack(Seq.getBeginLoc(), Context); |
431 | | |
432 | | // First, check if ParentMacroStack is not empty which means we are currently |
433 | | // dealing with a parent statement which was expanded from a macro. |
434 | | // If this parent statement was expanded from the same macros as this |
435 | | // statement, we reduce the initial complexity of this statement to zero. |
436 | | // This causes that a group of statements that were generated by a single |
437 | | // macro expansion will only increase the total complexity by one. |
438 | | // Note: This is not the final complexity of this statement as we still |
439 | | // add the complexity of the child statements to the complexity value. |
440 | 3.40k | if (!ParentMacroStack.empty() && MacroStack == ParentMacroStack1.36k ) { |
441 | 1.24k | Complexity = 0; |
442 | 1.24k | } |
443 | | |
444 | | // Iterate over the Stmts in the StmtSequence and add their complexity values |
445 | | // to the current complexity value. |
446 | 3.40k | if (Seq.holdsSequence()) { |
447 | 181 | for (const Stmt *S : Seq) { |
448 | 181 | Complexity += calculateStmtComplexity( |
449 | 181 | StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack); |
450 | 181 | if (Complexity >= Limit) |
451 | 57 | return Limit; |
452 | 181 | } |
453 | 3.31k | } else { |
454 | 3.31k | for (const Stmt *S : Seq.front()->children()) { |
455 | 2.80k | Complexity += calculateStmtComplexity( |
456 | 2.80k | StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack); |
457 | 2.80k | if (Complexity >= Limit) |
458 | 108 | return Limit; |
459 | 2.80k | } |
460 | 3.31k | } |
461 | 3.23k | return Complexity; |
462 | 3.40k | } |
463 | | |
464 | | void MatchingVariablePatternConstraint::constrain( |
465 | 27 | std::vector<CloneDetector::CloneGroup> &CloneGroups) { |
466 | 27 | CloneConstraint::splitCloneGroups( |
467 | 27 | CloneGroups, [](const StmtSequence &A, const StmtSequence &B) { |
468 | 19 | VariablePattern PatternA(A); |
469 | 19 | VariablePattern PatternB(B); |
470 | 19 | return PatternA.countPatternDifferences(PatternB) == 0; |
471 | 19 | }); |
472 | 27 | } |
473 | | |
474 | | void CloneConstraint::splitCloneGroups( |
475 | | std::vector<CloneDetector::CloneGroup> &CloneGroups, |
476 | | llvm::function_ref<bool(const StmtSequence &, const StmtSequence &)> |
477 | 58 | Compare) { |
478 | 58 | std::vector<CloneDetector::CloneGroup> Result; |
479 | 120 | for (auto &HashGroup : CloneGroups) { |
480 | | // Contains all indexes in HashGroup that were already added to a |
481 | | // CloneGroup. |
482 | 120 | std::vector<char> Indexes; |
483 | 120 | Indexes.resize(HashGroup.size()); |
484 | | |
485 | 412 | for (unsigned i = 0; i < HashGroup.size(); ++i292 ) { |
486 | | // Skip indexes that are already part of a CloneGroup. |
487 | 292 | if (Indexes[i]) |
488 | 168 | continue; |
489 | | |
490 | | // Pick the first unhandled StmtSequence and consider it as the |
491 | | // beginning |
492 | | // of a new CloneGroup for now. |
493 | | // We don't add i to Indexes because we never iterate back. |
494 | 124 | StmtSequence Prototype = HashGroup[i]; |
495 | 124 | CloneDetector::CloneGroup PotentialGroup = {Prototype}; |
496 | 124 | ++Indexes[i]; |
497 | | |
498 | | // Check all following StmtSequences for clones. |
499 | 297 | for (unsigned j = i + 1; j < HashGroup.size(); ++j173 ) { |
500 | | // Skip indexes that are already part of a CloneGroup. |
501 | 173 | if (Indexes[j]) |
502 | 0 | continue; |
503 | | |
504 | | // If a following StmtSequence belongs to our CloneGroup, we add it. |
505 | 173 | const StmtSequence &Candidate = HashGroup[j]; |
506 | | |
507 | 173 | if (!Compare(Prototype, Candidate)) |
508 | 5 | continue; |
509 | | |
510 | 168 | PotentialGroup.push_back(Candidate); |
511 | | // Make sure we never visit this StmtSequence again. |
512 | 168 | ++Indexes[j]; |
513 | 168 | } |
514 | | |
515 | | // Otherwise, add it to the result and continue searching for more |
516 | | // groups. |
517 | 124 | Result.push_back(PotentialGroup); |
518 | 124 | } |
519 | | |
520 | 120 | assert(llvm::all_of(Indexes, [](char c) { return c == 1; })); |
521 | 120 | } |
522 | 58 | CloneGroups = Result; |
523 | 58 | } |
524 | | |
525 | | void VariablePattern::addVariableOccurence(const VarDecl *VarDecl, |
526 | 549 | const Stmt *Mention) { |
527 | | // First check if we already reference this variable |
528 | 772 | for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex223 ) { |
529 | 589 | if (Variables[KindIndex] == VarDecl) { |
530 | | // If yes, add a new occurrence that points to the existing entry in |
531 | | // the Variables vector. |
532 | 366 | Occurences.emplace_back(KindIndex, Mention); |
533 | 366 | return; |
534 | 366 | } |
535 | 589 | } |
536 | | // If this variable wasn't already referenced, add it to the list of |
537 | | // referenced variables and add a occurrence that points to this new entry. |
538 | 183 | Occurences.emplace_back(Variables.size(), Mention); |
539 | 183 | Variables.push_back(VarDecl); |
540 | 183 | } |
541 | | |
542 | 2.48k | void VariablePattern::addVariables(const Stmt *S) { |
543 | | // Sometimes we get a nullptr (such as from IfStmts which often have nullptr |
544 | | // children). We skip such statements as they don't reference any |
545 | | // variables. |
546 | 2.48k | if (!S) |
547 | 0 | return; |
548 | | |
549 | | // Check if S is a reference to a variable. If yes, add it to the pattern. |
550 | 2.48k | if (auto D = dyn_cast<DeclRefExpr>(S)) { |
551 | 587 | if (auto VD = dyn_cast<VarDecl>(D->getDecl()->getCanonicalDecl())) |
552 | 549 | addVariableOccurence(VD, D); |
553 | 587 | } |
554 | | |
555 | | // Recursively check all children of the given statement. |
556 | 2.48k | for (const Stmt *Child : S->children()) { |
557 | 2.36k | addVariables(Child); |
558 | 2.36k | } |
559 | 2.48k | } |
560 | | |
561 | | unsigned VariablePattern::countPatternDifferences( |
562 | | const VariablePattern &Other, |
563 | 45 | VariablePattern::SuspiciousClonePair *FirstMismatch) { |
564 | 45 | unsigned NumberOfDifferences = 0; |
565 | | |
566 | 45 | assert(Other.Occurences.size() == Occurences.size()); |
567 | 278 | for (unsigned i = 0; i < Occurences.size(); ++i233 ) { |
568 | 233 | auto ThisOccurence = Occurences[i]; |
569 | 233 | auto OtherOccurence = Other.Occurences[i]; |
570 | 233 | if (ThisOccurence.KindID == OtherOccurence.KindID) |
571 | 220 | continue; |
572 | | |
573 | 13 | ++NumberOfDifferences; |
574 | | |
575 | | // If FirstMismatch is not a nullptr, we need to store information about |
576 | | // the first difference between the two patterns. |
577 | 13 | if (FirstMismatch == nullptr) |
578 | 3 | continue; |
579 | | |
580 | | // Only proceed if we just found the first difference as we only store |
581 | | // information about the first difference. |
582 | 10 | if (NumberOfDifferences != 1) |
583 | 2 | continue; |
584 | | |
585 | 8 | const VarDecl *FirstSuggestion = nullptr; |
586 | | // If there is a variable available in the list of referenced variables |
587 | | // which wouldn't break the pattern if it is used in place of the |
588 | | // current variable, we provide this variable as the suggested fix. |
589 | 8 | if (OtherOccurence.KindID < Variables.size()) |
590 | 5 | FirstSuggestion = Variables[OtherOccurence.KindID]; |
591 | | |
592 | | // Store information about the first clone. |
593 | 8 | FirstMismatch->FirstCloneInfo = |
594 | 8 | VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo( |
595 | 8 | Variables[ThisOccurence.KindID], ThisOccurence.Mention, |
596 | 8 | FirstSuggestion); |
597 | | |
598 | | // Same as above but with the other clone. We do this for both clones as |
599 | | // we don't know which clone is the one containing the unintended |
600 | | // pattern error. |
601 | 8 | const VarDecl *SecondSuggestion = nullptr; |
602 | 8 | if (ThisOccurence.KindID < Other.Variables.size()) |
603 | 8 | SecondSuggestion = Other.Variables[ThisOccurence.KindID]; |
604 | | |
605 | | // Store information about the second clone. |
606 | 8 | FirstMismatch->SecondCloneInfo = |
607 | 8 | VariablePattern::SuspiciousClonePair::SuspiciousCloneInfo( |
608 | 8 | Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention, |
609 | 8 | SecondSuggestion); |
610 | | |
611 | | // SuspiciousClonePair guarantees that the first clone always has a |
612 | | // suggested variable associated with it. As we know that one of the two |
613 | | // clones in the pair always has suggestion, we swap the two clones |
614 | | // in case the first clone has no suggested variable which means that |
615 | | // the second clone has a suggested variable and should be first. |
616 | 8 | if (!FirstMismatch->FirstCloneInfo.Suggestion) |
617 | 3 | std::swap(FirstMismatch->FirstCloneInfo, FirstMismatch->SecondCloneInfo); |
618 | | |
619 | | // This ensures that we always have at least one suggestion in a pair. |
620 | 8 | assert(FirstMismatch->FirstCloneInfo.Suggestion); |
621 | 8 | } |
622 | | |
623 | 45 | return NumberOfDifferences; |
624 | 45 | } |