Coverage Report

Created: 2020-02-25 14:32

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