//===--- CloneDetection.h - Finds code clones in an AST ---------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file defines classes for searching and analyzing source code clones.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_ANALYSIS_CLONEDETECTION_H
#define LLVM_CLANG_ANALYSIS_CLONEDETECTION_H
#include "clang/AST/StmtVisitor.h"
#include "llvm/Support/Regex.h"
#include <vector>
namespace clang {
class Stmt;
class Decl;
class VarDecl;
class ASTContext;
class CompoundStmt;
/// Identifies a list of statements.
///
/// Can either identify a single arbitrary Stmt object, a continuous sequence of
/// child statements inside a CompoundStmt or no statements at all.
class StmtSequence {
/// If this object identifies a sequence of statements inside a CompoundStmt,
/// S points to this CompoundStmt. If this object only identifies a single
/// Stmt, then S is a pointer to this Stmt.
const Stmt *S;
/// The declaration that contains the statements.
const Decl *D;
/// If EndIndex is non-zero, then S is a CompoundStmt and this StmtSequence
/// instance is representing the CompoundStmt children inside the array
/// [StartIndex, EndIndex).
unsigned StartIndex;
unsigned EndIndex;
public:
/// Constructs a StmtSequence holding multiple statements.
///
/// The resulting StmtSequence identifies a continuous sequence of statements
/// in the body of the given CompoundStmt. Which statements of the body should
/// be identified needs to be specified by providing a start and end index
/// that describe a non-empty sub-array in the body of the given CompoundStmt.
///
/// \param Stmt A CompoundStmt that contains all statements in its body.
/// \param D The Decl containing this Stmt.
/// \param StartIndex The inclusive start index in the children array of
/// \p Stmt
/// \param EndIndex The exclusive end index in the children array of \p Stmt.
StmtSequence(const CompoundStmt *Stmt, const Decl *D, unsigned StartIndex,
unsigned EndIndex);
/// Constructs a StmtSequence holding a single statement.
///
/// \param Stmt An arbitrary Stmt.
/// \param D The Decl containing this Stmt.
StmtSequence(const Stmt *Stmt, const Decl *D);
/// Constructs an empty StmtSequence.
StmtSequence();
typedef const Stmt *const *iterator;
/// Returns an iterator pointing to the first statement in this sequence.
iterator begin() const;
/// Returns an iterator pointing behind the last statement in this sequence.
iterator end() const;
/// Returns the first statement in this sequence.
///
/// This method should only be called on a non-empty StmtSequence object.
const Stmt *front() const {
assert(!empty());
return begin()[0];
}
/// Returns the last statement in this sequence.
///
/// This method should only be called on a non-empty StmtSequence object.
const Stmt *back() const {
assert(!empty());
return begin()[size() - 1];
}
/// Returns the number of statements this object holds.
unsigned size() const {
if (holdsSequence())
return EndIndex - StartIndex;
if (S == nullptr)
return 0;
return 1;
}
/// Returns true if and only if this StmtSequence contains no statements.
bool empty() const { return size() == 0; }
/// Returns the related ASTContext for the stored Stmts.
ASTContext &getASTContext() const;
/// Returns the declaration that contains the stored Stmts.
const Decl *getContainingDecl() const {
assert(D);
return D;
}
/// Returns true if this objects holds a list of statements.
bool holdsSequence() const { return EndIndex != 0; }
/// Returns the start sourcelocation of the first statement in this sequence.
///
/// This method should only be called on a non-empty StmtSequence object.
SourceLocation getBeginLoc() const;
/// Returns the end sourcelocation of the last statement in this sequence.
///
/// This method should only be called on a non-empty StmtSequence object.
SourceLocation getEndLoc() const;
/// Returns the source range of the whole sequence - from the beginning
/// of the first statement to the end of the last statement.
SourceRange getSourceRange() const;
bool operator==(const StmtSequence &Other) const {
return std::tie(S, StartIndex, EndIndex) ==
std::tie(Other.S, Other.StartIndex, Other.EndIndex);
}
bool operator!=(const StmtSequence &Other) const {
return std::tie(S, StartIndex, EndIndex) !=
std::tie(Other.S, Other.StartIndex, Other.EndIndex);
}
/// Returns true if and only if this sequence covers a source range that
/// contains the source range of the given sequence \p Other.
///
/// This method should only be called on a non-empty StmtSequence object
/// and passed a non-empty StmtSequence object.
bool contains(const StmtSequence &Other) const;
};
/// Searches for similar subtrees in the AST.
///
/// First, this class needs several declarations with statement bodies which
/// can be passed via analyzeCodeBody. Afterwards all statements can be
/// searched for clones by calling findClones with a given list of constraints
/// that should specify the wanted properties of the clones.
///
/// The result of findClones can be further constrained with the constrainClones
/// method.
///
/// This class only searches for clones in executable source code
/// (e.g. function bodies). Other clones (e.g. cloned comments or declarations)
/// are not supported.
class CloneDetector {
public:
/// A collection of StmtSequences that share an arbitrary property.
typedef llvm::SmallVector<StmtSequence, 8> CloneGroup;
/// Generates and stores search data for all statements in the body of
/// the given Decl.
void analyzeCodeBody(const Decl *D);
/// Constrains the given list of clone groups with the given constraint.
///
/// The constraint is expected to have a method with the signature
/// `void constrain(std::vector<CloneDetector::CloneGroup> &Sequences)`
/// as this is the interface that the CloneDetector uses for applying the
/// constraint. The constraint is supposed to directly modify the passed list
/// so that all clones in the list fulfill the specific property this
/// constraint ensures.
template <typename T>
static void constrainClones(std::vector<CloneGroup> &CloneGroups, T C) {
C.constrain(CloneGroups);
}
/// Constrains the given list of clone groups with the given list of
/// constraints.
///
/// The constraints are applied in sequence in the order in which they are
/// passed to this function.
template <typename T1, typename... Ts>
static void constrainClones(std::vector<CloneGroup> &CloneGroups, T1 C,
Ts... ConstraintList) {
constrainClones(CloneGroups, C);
constrainClones(CloneGroups, ConstraintList...);
}
/// Searches for clones in all previously passed statements.
/// \param Result Output parameter to which all created clone groups are
/// added.
/// \param ConstraintList The constraints that should be applied to the
// result.
template <typename... Ts>
void findClones(std::vector<CloneGroup> &Result, Ts... ConstraintList) {
// The initial assumption is that there is only one clone group and every
// statement is a clone of the others. This clone group will then be
// split up with the help of the constraints.
Result.push_back(Sequences);
constrainClones(Result, ConstraintList...);
}
private:
CloneGroup Sequences;
};
/// This class is a utility class that contains utility functions for building
/// custom constraints.
class CloneConstraint {
public:
/// Removes all groups by using a filter function.
/// \param CloneGroups The list of CloneGroups that is supposed to be
/// filtered.
/// \param Filter The filter function that should return true for all groups
/// that should be removed from the list.
static void filterGroups(
std::vector<CloneDetector::CloneGroup> &CloneGroups,
llvm::function_ref<bool(const CloneDetector::CloneGroup &)> Filter) {
llvm::erase_if(CloneGroups, Filter);
}
/// Splits the given CloneGroups until the given Compare function returns true
/// for all clones in a single group.
/// \param CloneGroups A list of CloneGroups that should be modified.
/// \param Compare The comparison function that all clones are supposed to
/// pass. Should return true if and only if two clones belong
/// to the same CloneGroup.
static void splitCloneGroups(
std::vector<CloneDetector::CloneGroup> &CloneGroups,
llvm::function_ref<bool(const StmtSequence &, const StmtSequence &)>
Compare);
};
/// This constraint moves clones into clone groups of type II via hashing.
///
/// Clones with different hash values are moved into separate clone groups.
/// Collisions are possible, and this constraint does nothing to address this
/// them. Add the slower RecursiveCloneTypeIIVerifyConstraint later in the
/// constraint chain, not necessarily immediately, to eliminate hash collisions
/// through a more detailed analysis.
class RecursiveCloneTypeIIHashConstraint {
public:
void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
};
/// This constraint moves clones into clone groups of type II by comparing them.
///
/// Clones that aren't type II clones are moved into separate clone groups.
/// In contrast to the RecursiveCloneTypeIIHashConstraint, all clones in a clone
/// group are guaranteed to be type II clones of each other, but it is too
/// slow to efficiently handle large amounts of clones.
class RecursiveCloneTypeIIVerifyConstraint {
public:
void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
};
/// Ensures that every clone has at least the given complexity.
///
/// Complexity is here defined as the total amount of children of a statement.
/// This constraint assumes the first statement in the group is representative
/// for all other statements in the group in terms of complexity.
class MinComplexityConstraint {
unsigned MinComplexity;
public:
MinComplexityConstraint(unsigned MinComplexity)
: MinComplexity(MinComplexity) {}
/// Calculates the complexity of the given StmtSequence.
/// \param Limit The limit of complexity we probe for. After reaching
/// this limit during calculation, this method is exiting
/// early to improve performance and returns this limit.
size_t calculateStmtComplexity(const StmtSequence &Seq, std::size_t Limit,
const std::string &ParentMacroStack = "");
void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups) {
CloneConstraint::filterGroups(
CloneGroups, [this](const CloneDetector::CloneGroup &A) {
if (!A.empty())
return calculateStmtComplexity(A.front(), MinComplexity) <
MinComplexity;
else
return false;
});
}
};
/// Ensures that all clone groups contain at least the given amount of clones.
class MinGroupSizeConstraint {
unsigned MinGroupSize;
public:
MinGroupSizeConstraint(unsigned MinGroupSize = 2)
: MinGroupSize(MinGroupSize) {}
void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups) {
CloneConstraint::filterGroups(CloneGroups,
[this](const CloneDetector::CloneGroup &A) {
return A.size() < MinGroupSize;
});
}
};
/// Ensures that no clone group fully contains another clone group.
struct OnlyLargestCloneConstraint {
void constrain(std::vector<CloneDetector::CloneGroup> &Result);
};
struct FilenamePatternConstraint {
StringRef IgnoredFilesPattern;
std::shared_ptr<llvm::Regex> IgnoredFilesRegex;
FilenamePatternConstraint(StringRef IgnoredFilesPattern)
: IgnoredFilesPattern(IgnoredFilesPattern) {
IgnoredFilesRegex = std::make_shared<llvm::Regex>("^(" +
IgnoredFilesPattern.str() + "$)");
}
bool isAutoGenerated(const CloneDetector::CloneGroup &Group);
void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups) {
CloneConstraint::filterGroups(
CloneGroups, [this](const CloneDetector::CloneGroup &Group) {
return isAutoGenerated(Group);
});
}
};
/// Analyzes the pattern of the referenced variables in a statement.
class VariablePattern {
/// Describes an occurrence of a variable reference in a statement.
struct VariableOccurence {
/// The index of the associated VarDecl in the Variables vector.
size_t KindID;
/// The statement in the code where the variable was referenced.
const Stmt *Mention;
VariableOccurence(size_t KindID, const Stmt *Mention)
: KindID(KindID), Mention(Mention) {}
};
/// All occurrences of referenced variables in the order of appearance.
std::vector<VariableOccurence> Occurences;
/// List of referenced variables in the order of appearance.
/// Every item in this list is unique.
std::vector<const VarDecl *> Variables;
/// Adds a new variable referenced to this pattern.
/// \param VarDecl The declaration of the variable that is referenced.
/// \param Mention The SourceRange where this variable is referenced.
void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention);
/// Adds each referenced variable from the given statement.
void addVariables(const Stmt *S);
public:
/// Creates an VariablePattern object with information about the given
/// StmtSequence.
VariablePattern(const StmtSequence &Sequence) {
for (const Stmt *S : Sequence)
addVariables(S);
}
/// Describes two clones that reference their variables in a different pattern
/// which could indicate a programming error.
struct SuspiciousClonePair {
/// Utility class holding the relevant information about a single
/// clone in this pair.
struct SuspiciousCloneInfo {
/// The variable which referencing in this clone was against the pattern.
const VarDecl *Variable;
/// Where the variable was referenced.
const Stmt *Mention;
/// The variable that should have been referenced to follow the pattern.
/// If Suggestion is a nullptr then it's not possible to fix the pattern
/// by referencing a different variable in this clone.
const VarDecl *Suggestion;
SuspiciousCloneInfo(const VarDecl *Variable, const Stmt *Mention,
const VarDecl *Suggestion)
: Variable(Variable), Mention(Mention), Suggestion(Suggestion) {}
SuspiciousCloneInfo() {}
};
/// The first clone in the pair which always has a suggested variable.
SuspiciousCloneInfo FirstCloneInfo;
/// This other clone in the pair which can have a suggested variable.
SuspiciousCloneInfo SecondCloneInfo;
};
/// Counts the differences between this pattern and the given one.
/// \param Other The given VariablePattern to compare with.
/// \param FirstMismatch Output parameter that will be filled with information
/// about the first difference between the two patterns. This parameter
/// can be a nullptr, in which case it will be ignored.
/// \return Returns the number of differences between the pattern this object
/// is following and the given VariablePattern.
///
/// For example, the following statements all have the same pattern and this
/// function would return zero:
///
/// if (a < b) return a; return b;
/// if (x < y) return x; return y;
/// if (u2 < u1) return u2; return u1;
///
/// But the following statement has a different pattern (note the changed
/// variables in the return statements) and would have two differences when
/// compared with one of the statements above.
///
/// if (a < b) return b; return a;
///
/// This function should only be called if the related statements of the given
/// pattern and the statements of this objects are clones of each other.
unsigned countPatternDifferences(
const VariablePattern &Other,
VariablePattern::SuspiciousClonePair *FirstMismatch = nullptr);
};
/// Ensures that all clones reference variables in the same pattern.
struct MatchingVariablePatternConstraint {
void constrain(std::vector<CloneDetector::CloneGroup> &CloneGroups);
};
} // end namespace clang
#endif // LLVM_CLANG_ANALYSIS_CLONEDETECTION_H