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