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