Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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
15
#include "clang/AST/DataCollection.h"
16
#include "clang/AST/DeclTemplate.h"
17
#include "llvm/Support/MD5.h"
18
#include "llvm/Support/Path.h"
19
20
using namespace clang;
21
22
StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D,
23
                           unsigned StartIndex, unsigned EndIndex)
24
304
    : S(Stmt), D(D), StartIndex(StartIndex), EndIndex(EndIndex) {
25
304
  assert(Stmt && "Stmt must not be a nullptr");
26
304
  assert(StartIndex < EndIndex && "Given array should not be empty");
27
304
  assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt");
28
304
}
29
30
StmtSequence::StmtSequence(const Stmt *Stmt, const Decl *D)
31
10.7k
    : S(Stmt), D(D), StartIndex(0), EndIndex(0) {}
32
33
StmtSequence::StmtSequence()
34
0
    : S(nullptr), D(nullptr), StartIndex(0), EndIndex(0) {}
35
36
1.15k
bool StmtSequence::contains(const StmtSequence &Other) const {
37
1.15k
  // If both sequences reside in different declarations, they can never contain
38
1.15k
  // each other.
39
1.15k
  if (D != Other.D)
40
812
    return false;
41
345
42
345
  const SourceManager &SM = getASTContext().getSourceManager();
43
345
44
345
  // Otherwise check if the start and end locations of the current sequence
45
345
  // surround the other sequence.
46
345
  bool StartIsInBounds =
47
345
      SM.isBeforeInTranslationUnit(getBeginLoc(), Other.getBeginLoc()) ||
48
345
      
getBeginLoc() == Other.getBeginLoc()182
;
49
345
  if (!StartIsInBounds)
50
135
    return false;
51
210
52
210
  bool EndIsInBounds =
53
210
      SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) ||
54
210
      
Other.getEndLoc() == getEndLoc()47
;
55
210
  return EndIsInBounds;
56
210
}
57
58
14.7k
StmtSequence::iterator StmtSequence::begin() const {
59
14.7k
  if (!holdsSequence()) {
60
13.3k
    return &S;
61
13.3k
  }
62
1.36k
  auto CS = cast<CompoundStmt>(S);
63
1.36k
  return CS->body_begin() + StartIndex;
64
1.36k
}
65
66
6.35k
StmtSequence::iterator StmtSequence::end() const {
67
6.35k
  if (!holdsSequence()) {
68
6.09k
    return reinterpret_cast<StmtSequence::iterator>(&S) + 1;
69
6.09k
  }
70
262
  auto CS = cast<CompoundStmt>(S);
71
262
  return CS->body_begin() + EndIndex;
72
262
}
73
74
10.3k
ASTContext &StmtSequence::getASTContext() const {
75
10.3k
  assert(D);
76
10.3k
  return D->getASTContext();
77
10.3k
}
78
79
4.45k
SourceLocation StmtSequence::getBeginLoc() const {
80
4.45k
  return front()->getBeginLoc();
81
4.45k
}
82
83
539
SourceLocation StmtSequence::getEndLoc() const { return back()->getEndLoc(); }
84
85
25
SourceRange StmtSequence::getSourceRange() const {
86
25
  return SourceRange(getBeginLoc(), getEndLoc());
87
25
}
88
89
97
void CloneDetector::analyzeCodeBody(const Decl *D) {
90
97
  assert(D);
91
97
  assert(D->hasBody());
92
97
93
97
  Sequences.push_back(StmtSequence(D->getBody(), D));
94
97
}
95
96
/// Returns true if and only if \p Stmt contains at least one other
97
/// sequence in the \p Group.
98
static bool containsAnyInGroup(StmtSequence &Seq,
99
549
                               CloneDetector::CloneGroup &Group) {
100
1.15k
  for (StmtSequence &GroupSeq : Group) {
101
1.15k
    if (Seq.contains(GroupSeq))
102
199
      return true;
103
1.15k
  }
104
549
  
return false350
;
105
549
}
106
107
/// Returns true if and only if all sequences in \p OtherGroup are
108
/// contained by a sequence in \p Group.
109
static bool containsGroup(CloneDetector::CloneGroup &Group,
110
509
                          CloneDetector::CloneGroup &OtherGroup) {
111
509
  // We have less sequences in the current group than we have in the other,
112
509
  // so we will never fulfill the requirement for returning true. This is only
113
509
  // possible because we know that a sequence in Group can contain at most
114
509
  // one sequence in OtherGroup.
115
509
  if (Group.size() < OtherGroup.size())
116
81
    return false;
117
428
118
549
  
for (StmtSequence &Stmt : Group)428
{
119
549
    if (!containsAnyInGroup(Stmt, OtherGroup))
120
350
      return false;
121
549
  }
122
428
  
return true78
;
123
428
}
124
125
void OnlyLargestCloneConstraint::constrain(
126
30
    std::vector<CloneDetector::CloneGroup> &Result) {
127
30
  std::vector<unsigned> IndexesToRemove;
128
30
129
30
  // Compare every group in the result with the rest. If one groups contains
130
30
  // another group, we only need to return the bigger group.
131
30
  // Note: This doesn't scale well, so if possible avoid calling any heavy
132
30
  // function from this loop to minimize the performance impact.
133
127
  for (unsigned i = 0; i < Result.size(); 
++i97
) {
134
560
    for (unsigned j = 0; j < Result.size(); 
++j463
) {
135
541
      // Don't compare a group with itself.
136
541
      if (i == j)
137
32
        continue;
138
509
139
509
      if (containsGroup(Result[j], Result[i])) {
140
78
        IndexesToRemove.push_back(i);
141
78
        break;
142
78
      }
143
509
    }
144
97
  }
145
30
146
30
  // Erasing a list of indexes from the vector should be done with decreasing
147
30
  // indexes. As IndexesToRemove is constructed with increasing values, we just
148
30
  // reverse iterate over it to get the desired order.
149
108
  for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); 
++I78
) {
150
78
    Result.erase(Result.begin() + *I);
151
78
  }
152
30
}
153
154
bool FilenamePatternConstraint::isAutoGenerated(
155
28
    const CloneDetector::CloneGroup &Group) {
156
28
  std::string Error;
157
28
  if (IgnoredFilesPattern.empty() || Group.empty() ||
158
28
      
!IgnoredFilesRegex->isValid(Error)27
)
159
1
    return false;
160
27
161
93
  
for (const StmtSequence &S : Group)27
{
162
93
    const SourceManager &SM = S.getASTContext().getSourceManager();
163
93
    StringRef Filename = llvm::sys::path::filename(
164
93
        SM.getFilename(S.getContainingDecl()->getLocation()));
165
93
    if (IgnoredFilesRegex->match(Filename))
166
4
      return true;
167
93
  }
168
27
169
27
  
return false23
;
170
27
}
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
35.4k
  template <class Ty> void addData(const Ty &Data) {
188
35.4k
    data_collection::addDataToConsumer(DataConsumer, Data);
189
35.4k
  }
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.71k
  template <class Ty> void addData(const Ty &Data) {
188
3.71k
    data_collection::addDataToConsumer(DataConsumer, Data);
189
3.71k
  }
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.83k
  template <class Ty> void addData(const Ty &Data) {
188
1.83k
    data_collection::addDataToConsumer(DataConsumer, Data);
189
1.83k
  }
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<clang::QualType>(clang::QualType const&)
Line
Count
Source
187
1.47k
  template <class Ty> void addData(const Ty &Data) {
188
1.47k
    data_collection::addDataToConsumer(DataConsumer, Data);
189
1.47k
  }
CloneDetection.cpp:void (anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::addData<unsigned int>(unsigned int const&)
Line
Count
Source
187
26
  template <class Ty> void addData(const Ty &Data) {
188
26
    data_collection::addDataToConsumer(DataConsumer, Data);
189
26
  }
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
285
  template <class Ty> void addData(const Ty &Data) {
188
285
    data_collection::addDataToConsumer(DataConsumer, Data);
189
285
  }
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
54
  template <class Ty> void addData(const Ty &Data) {
188
54
    data_collection::addDataToConsumer(DataConsumer, Data);
189
54
  }
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.37k
      : Context(Context), DataConsumer(DataConsumer) {
195
8.37k
    this->Visit(S);
196
8.37k
  }
CloneDetection.cpp:(anonymous namespace)::CloneTypeIIStmtDataCollector<llvm::MD5>::CloneTypeIIStmtDataCollector(clang::Stmt const*, clang::ASTContext&, llvm::MD5&)
Line
Count
Source
194
1.83k
      : Context(Context), DataConsumer(DataConsumer) {
195
1.83k
    this->Visit(S);
196
1.83k
  }
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.6k
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
18.6k
    
CODE470
; \
204
18.6k
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
18.6k
  }
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.83k
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
1.83k
    CODE;                                                                      \
204
1.83k
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
1.83k
  }
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
26
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
78
    CODE;                                                                      \
204
26
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
26
  }
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.43k
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
1.43k
    CODE;                                                                      \
204
1.43k
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
1.43k
  }
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
285
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
285
    CODE;                                                                      \
204
285
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
285
  }
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
33
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
137
    CODE;                                                                      \
204
33
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
33
  }
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
54
  template <class = void> void Visit##CLASS(const CLASS *S) {                  \
203
54
    CODE;                                                                      \
204
54
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
205
54
  }
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.53k
  void Visit##CLASS(const CLASS *S) {                                          \
212
3.53k
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
213
3.53k
  }
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
411
  void Visit##CLASS(const CLASS *S) {                                          \
212
411
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
213
411
  }
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
206
  void Visit##CLASS(const CLASS *S) {                                          \
212
206
    ConstStmtVisitor<CloneTypeIIStmtDataCollector<T>>::Visit##CLASS(S);        \
213
206
  }
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
2.14k
static size_t createHash(llvm::MD5 &Hash) {
226
2.14k
  size_t HashCode;
227
2.14k
228
2.14k
  // Create the final hash code for the current Stmt.
229
2.14k
  llvm::MD5::MD5Result HashResult;
230
2.14k
  Hash.final(HashResult);
231
2.14k
232
2.14k
  // Copy as much as possible of the generated hash code to the Stmt's hash
233
2.14k
  // code.
234
2.14k
  std::memcpy(&HashCode, &HashResult,
235
2.14k
              std::min(sizeof(HashCode), sizeof(HashResult)));
236
2.14k
237
2.14k
  return HashCode;
238
2.14k
}
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.83k
         std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) {
252
1.83k
  llvm::MD5 Hash;
253
1.83k
  ASTContext &Context = D->getASTContext();
254
1.83k
255
1.83k
  CloneTypeIIStmtDataCollector<llvm::MD5>(S, Context, Hash);
256
1.83k
257
1.83k
  auto CS = dyn_cast<CompoundStmt>(S);
258
1.83k
  SmallVector<size_t, 8> ChildHashes;
259
1.83k
260
1.83k
  for (const Stmt *Child : S->children()) {
261
1.74k
    if (Child == nullptr) {
262
2
      ChildHashes.push_back(0);
263
2
      continue;
264
2
    }
265
1.74k
    size_t ChildHash = saveHash(Child, D, StmtsByHash);
266
1.74k
    Hash.update(
267
1.74k
        StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));
268
1.74k
    ChildHashes.push_back(ChildHash);
269
1.74k
  }
270
1.83k
271
1.83k
  if (CS) {
272
133
    // If we're in a CompoundStmt, we hash all possible combinations of child
273
133
    // statements to find clones in those subsequences.
274
133
    // We first go through every possible starting position of a subsequence.
275
415
    for (unsigned Pos = 0; Pos < CS->size(); 
++Pos282
) {
276
282
      // Then we try all possible lengths this subsequence could have and
277
282
      // reuse the same hash object to make sure we only hash every child
278
282
      // hash exactly once.
279
282
      llvm::MD5 Hash;
280
868
      for (unsigned Length = 1; Length <= CS->size() - Pos; 
++Length586
) {
281
586
        // Grab the current child hash and put it into our hash. We do
282
586
        // -1 on the index because we start counting the length at 1.
283
586
        size_t ChildHash = ChildHashes[Pos + Length - 1];
284
586
        Hash.update(
285
586
            StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));
286
586
        // If we have at least two elements in our subsequence, we can start
287
586
        // saving it.
288
586
        if (Length > 1) {
289
304
          llvm::MD5 SubHash = Hash;
290
304
          StmtsByHash.push_back(std::make_pair(
291
304
              createHash(SubHash), StmtSequence(CS, D, Pos, Pos + Length)));
292
304
        }
293
586
      }
294
282
    }
295
133
  }
296
1.83k
297
1.83k
  size_t HashCode = createHash(Hash);
298
1.83k
  StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D)));
299
1.83k
  return HashCode;
300
1.83k
}
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
6.53k
324
6.53k
    for (const Stmt *Child : S->children()) {
325
5.89k
      if (!Child)
326
0
        continue;
327
5.89k
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
145
  // We collect the data from all statements in the sequence as we did before
338
145
  // when generating a hash value for each sequence. But this time we don't
339
145
  // hash the collected data and compare the whole data set instead. This
340
145
  // 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
145
345
145
  CollectStmtSequenceData(LHS, LHSWrapper);
346
145
  CollectStmtSequenceData(RHS, RHSWrapper);
347
145
348
145
  return DataLHS == DataRHS;
349
145
}
350
351
void RecursiveCloneTypeIIHashConstraint::constrain(
352
30
    std::vector<CloneDetector::CloneGroup> &Sequences) {
353
30
  // FIXME: Maybe we can do this in-place and don't need this additional vector.
354
30
  std::vector<CloneDetector::CloneGroup> Result;
355
30
356
30
  for (CloneDetector::CloneGroup &Group : Sequences) {
357
28
    // We assume in the following code that the Group is non-empty, so we
358
28
    // skip all empty groups.
359
28
    if (Group.empty())
360
1
      continue;
361
27
362
27
    std::vector<std::pair<size_t, StmtSequence>> StmtsByHash;
363
27
364
27
    // Generate hash codes for all children of S and save them in StmtsByHash.
365
97
    for (const StmtSequence &S : Group) {
366
97
      saveHash(S.front(), S.getContainingDecl(), StmtsByHash);
367
97
    }
368
27
369
27
    // Sort hash_codes in StmtsByHash.
370
27
    llvm::stable_sort(StmtsByHash, llvm::less_first());
371
27
372
27
    // Check for each StmtSequence if its successor has the same hash value.
373
27
    // We don't check the last StmtSequence as it has no successor.
374
27
    // Note: The 'size - 1 ' in the condition is safe because we check for an
375
27
    // empty Group vector at the beginning of this function.
376
770
    for (unsigned i = 0; i < StmtsByHash.size() - 1; 
++i743
) {
377
743
      const auto Current = StmtsByHash[i];
378
743
379
743
      // It's likely that we just found a sequence of StmtSequences that
380
743
      // represent a CloneGroup, so we create a new group and start checking and
381
743
      // adding the StmtSequences in this sequence.
382
743
      CloneDetector::CloneGroup NewGroup;
383
743
384
743
      size_t PrototypeHash = Current.first;
385
743
386
2.87k
      for (; i < StmtsByHash.size(); 
++i2.13k
) {
387
2.85k
        // A different hash value means we have reached the end of the sequence.
388
2.85k
        if (PrototypeHash != StmtsByHash[i].first) {
389
726
          // The current sequence could be the start of a new CloneGroup. So we
390
726
          // decrement i so that we visit it again in the outer loop.
391
726
          // Note: i can never be 0 at this point because we are just comparing
392
726
          // the hash of the Current StmtSequence with itself in the 'if' above.
393
726
          assert(i != 0);
394
726
          --i;
395
726
          break;
396
726
        }
397
2.13k
        // Same hash value means we should add the StmtSequence to the current
398
2.13k
        // group.
399
2.13k
        NewGroup.push_back(StmtsByHash[i].second);
400
2.13k
      }
401
743
402
743
      // We created a new clone group with matching hash codes and move it to
403
743
      // the result vector.
404
743
      Result.push_back(NewGroup);
405
743
    }
406
27
  }
407
30
  // Sequences is the output parameter, so we copy our result into it.
408
30
  Sequences = Result;
409
30
}
410
411
void RecursiveCloneTypeIIVerifyConstraint::constrain(
412
30
    std::vector<CloneDetector::CloneGroup> &Sequences) {
413
30
  CloneConstraint::splitCloneGroups(
414
145
      Sequences, [](const StmtSequence &A, const StmtSequence &B) {
415
145
        return areSequencesClones(A, B);
416
145
      });
417
30
}
418
419
size_t MinComplexityConstraint::calculateStmtComplexity(
420
    const StmtSequence &Seq, std::size_t Limit,
421
3.37k
    const std::string &ParentMacroStack) {
422
3.37k
  if (Seq.empty())
423
0
    return 0;
424
3.37k
425
3.37k
  size_t Complexity = 1;
426
3.37k
427
3.37k
  ASTContext &Context = Seq.getASTContext();
428
3.37k
429
3.37k
  // Look up what macros expanded into the current statement.
430
3.37k
  std::string MacroStack =
431
3.37k
      data_collection::getMacroStack(Seq.getBeginLoc(), Context);
432
3.37k
433
3.37k
  // First, check if ParentMacroStack is not empty which means we are currently
434
3.37k
  // dealing with a parent statement which was expanded from a macro.
435
3.37k
  // If this parent statement was expanded from the same macros as this
436
3.37k
  // statement, we reduce the initial complexity of this statement to zero.
437
3.37k
  // This causes that a group of statements that were generated by a single
438
3.37k
  // macro expansion will only increase the total complexity by one.
439
3.37k
  // Note: This is not the final complexity of this statement as we still
440
3.37k
  // add the complexity of the child statements to the complexity value.
441
3.37k
  if (!ParentMacroStack.empty() && 
MacroStack == ParentMacroStack1.35k
) {
442
1.23k
    Complexity = 0;
443
1.23k
  }
444
3.37k
445
3.37k
  // Iterate over the Stmts in the StmtSequence and add their complexity values
446
3.37k
  // to the current complexity value.
447
3.37k
  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.29k
  } else {
455
3.29k
    for (const Stmt *S : Seq.front()->children()) {
456
2.78k
      Complexity += calculateStmtComplexity(
457
2.78k
          StmtSequence(S, Seq.getContainingDecl()), Limit, MacroStack);
458
2.78k
      if (Complexity >= Limit)
459
100
        return Limit;
460
2.78k
    }
461
3.29k
  }
462
3.37k
  
return Complexity3.21k
;
463
3.37k
}
464
465
void MatchingVariablePatternConstraint::constrain(
466
27
    std::vector<CloneDetector::CloneGroup> &CloneGroups) {
467
27
  CloneConstraint::splitCloneGroups(
468
27
      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
27
}
474
475
void CloneConstraint::splitCloneGroups(
476
    std::vector<CloneDetector::CloneGroup> &CloneGroups,
477
    llvm::function_ref<bool(const StmtSequence &, const StmtSequence &)>
478
58
        Compare) {
479
58
  std::vector<CloneDetector::CloneGroup> Result;
480
111
  for (auto &HashGroup : CloneGroups) {
481
111
    // Contains all indexes in HashGroup that were already added to a
482
111
    // CloneGroup.
483
111
    std::vector<char> Indexes;
484
111
    Indexes.resize(HashGroup.size());
485
111
486
385
    for (unsigned i = 0; i < HashGroup.size(); 
++i274
) {
487
274
      // Skip indexes that are already part of a CloneGroup.
488
274
      if (Indexes[i])
489
159
        continue;
490
115
491
115
      // Pick the first unhandled StmtSequence and consider it as the
492
115
      // beginning
493
115
      // of a new CloneGroup for now.
494
115
      // 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
115
499
115
      // Check all following StmtSequences for clones.
500
279
      for (unsigned j = i + 1; j < HashGroup.size(); 
++j164
) {
501
164
        // Skip indexes that are already part of a CloneGroup.
502
164
        if (Indexes[j])
503
0
          continue;
504
164
505
164
        // If a following StmtSequence belongs to our CloneGroup, we add it.
506
164
        const StmtSequence &Candidate = HashGroup[j];
507
164
508
164
        if (!Compare(Prototype, Candidate))
509
5
          continue;
510
159
511
159
        PotentialGroup.push_back(Candidate);
512
159
        // Make sure we never visit this StmtSequence again.
513
159
        ++Indexes[j];
514
159
      }
515
115
516
115
      // Otherwise, add it to the result and continue searching for more
517
115
      // groups.
518
115
      Result.push_back(PotentialGroup);
519
115
    }
520
111
521
111
    assert(llvm::all_of(Indexes, [](char c) { return c == 1; }));
522
111
  }
523
58
  CloneGroups = Result;
524
58
}
525
526
void VariablePattern::addVariableOccurence(const VarDecl *VarDecl,
527
524
                                           const Stmt *Mention) {
528
524
  // 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
361
      // If yes, add a new occurrence that points to the existing entry in
532
361
      // the Variables vector.
533
361
      Occurences.emplace_back(KindIndex, Mention);
534
361
      return;
535
361
    }
536
584
  }
537
524
  // If this variable wasn't already referenced, add it to the list of
538
524
  // referenced variables and add a occurrence that points to this new entry.
539
524
  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
2.30k
  // Sometimes we get a nullptr (such as from IfStmts which often have nullptr
545
2.30k
  // children). We skip such statements as they don't reference any
546
2.30k
  // variables.
547
2.30k
  if (!S)
548
0
    return;
549
2.30k
550
2.30k
  // 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
2.30k
556
2.30k
  // Recursively check all children of the given statement.
557
2.30k
  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
37
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
13
574
13
    ++NumberOfDifferences;
575
13
576
13
    // If FirstMismatch is not a nullptr, we need to store information about
577
13
    // the first difference between the two patterns.
578
13
    if (FirstMismatch == nullptr)
579
3
      continue;
580
10
581
10
    // Only proceed if we just found the first difference as we only store
582
10
    // information about the first difference.
583
10
    if (NumberOfDifferences != 1)
584
2
      continue;
585
8
586
8
    const VarDecl *FirstSuggestion = nullptr;
587
8
    // If there is a variable available in the list of referenced variables
588
8
    // which wouldn't break the pattern if it is used in place of the
589
8
    // current variable, we provide this variable as the suggested fix.
590
8
    if (OtherOccurence.KindID < Variables.size())
591
5
      FirstSuggestion = Variables[OtherOccurence.KindID];
592
8
593
8
    // 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
8
599
8
    // Same as above but with the other clone. We do this for both clones as
600
8
    // we don't know which clone is the one containing the unintended
601
8
    // pattern error.
602
8
    const VarDecl *SecondSuggestion = nullptr;
603
8
    if (ThisOccurence.KindID < Other.Variables.size())
604
8
      SecondSuggestion = Other.Variables[ThisOccurence.KindID];
605
8
606
8
    // 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
8
612
8
    // SuspiciousClonePair guarantees that the first clone always has a
613
8
    // suggested variable associated with it. As we know that one of the two
614
8
    // clones in the pair always has suggestion, we swap the two clones
615
8
    // in case the first clone has no suggested variable which means that
616
8
    // 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
8
620
8
    // This ensures that we always have at least one suggestion in a pair.
621
8
    assert(FirstMismatch->FirstCloneInfo.Suggestion);
622
8
  }
623
37
624
37
  return NumberOfDifferences;
625
37
}