| 1 |
//===--- InefficientAlgorithmCheck.cpp - clang-tidy------------------------===// |
| 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 |
#include "InefficientAlgorithmCheck.h" |
| 10 |
#include "clang/AST/ASTContext.h" |
| 11 |
#include "clang/ASTMatchers/ASTMatchFinder.h" |
| 12 |
#include "clang/Lex/Lexer.h" |
| 13 |
|
| 14 |
using namespace clang::ast_matchers; |
| 15 |
|
| 16 |
namespace clang::tidy::performance { |
| 17 |
|
| 18 |
static bool areTypesCompatible(QualType Left, QualType Right) { |
| 19 |
if (const auto *LeftRefType = Left->getAs<ReferenceType>()) |
| 20 |
Left = LeftRefType->getPointeeType(); |
| 21 |
if (const auto *RightRefType = Right->getAs<ReferenceType>()) |
| 22 |
Right = RightRefType->getPointeeType(); |
| 23 |
return Left->getCanonicalTypeUnqualified() == |
| 24 |
Right->getCanonicalTypeUnqualified(); |
| 25 |
} |
| 26 |
|
| 27 |
void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) { |
| 28 |
const auto Algorithms = |
| 29 |
hasAnyName("::std::find", "::std::count", "::std::equal_range", |
| 30 |
"::std::lower_bound", "::std::upper_bound"); |
| 31 |
const auto ContainerMatcher = classTemplateSpecializationDecl(hasAnyName( |
| 32 |
"::std::set", "::std::map", "::std::multiset", "::std::multimap", |
| 33 |
"::std::unordered_set", "::std::unordered_map", |
| 34 |
"::std::unordered_multiset", "::std::unordered_multimap")); |
| 35 |
|
| 36 |
const auto Matcher = |
| 37 |
callExpr( |
| 38 |
callee(functionDecl(Algorithms)), |
| 39 |
hasArgument( |
| 40 |
0, cxxMemberCallExpr( |
| 41 |
callee(cxxMethodDecl(hasName("begin"))), |
| 42 |
on(declRefExpr( |
| 43 |
hasDeclaration(decl().bind("IneffContObj")), |
| 44 |
anyOf(hasType(ContainerMatcher.bind("IneffCont")), |
| 45 |
hasType(pointsTo( |
| 46 |
ContainerMatcher.bind("IneffContPtr"))))) |
| 47 |
.bind("IneffContExpr")))), |
| 48 |
hasArgument( |
| 49 |
1, cxxMemberCallExpr(callee(cxxMethodDecl(hasName("end"))), |
| 50 |
on(declRefExpr(hasDeclaration( |
| 51 |
equalsBoundNode("IneffContObj")))))), |
| 52 |
hasArgument(2, expr().bind("AlgParam"))) |
| 53 |
.bind("IneffAlg"); |
| 54 |
|
| 55 |
Finder->addMatcher(Matcher, this); |
| 56 |
} |
| 57 |
|
| 58 |
void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) { |
| 59 |
const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>("IneffAlg"); |
| 60 |
const auto *IneffCont = |
| 61 |
Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffCont"); |
| 62 |
bool PtrToContainer = false; |
| 63 |
if (!IneffCont) { |
| 64 |
IneffCont = |
| 65 |
Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffContPtr"); |
| 66 |
PtrToContainer = true; |
| 67 |
} |
| 68 |
const llvm::StringRef IneffContName = IneffCont->getName(); |
| 69 |
const bool Unordered = IneffContName.contains("unordered"); |
| 70 |
const bool Maplike = IneffContName.contains("map"); |
| 71 |
|
| 72 |
// Store if the key type of the container is compatible with the value |
| 73 |
// that is searched for. |
| 74 |
QualType ValueType = AlgCall->getArg(2)->getType(); |
| 75 |
QualType KeyType = |
| 76 |
IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType(); |
| 77 |
const bool CompatibleTypes = areTypesCompatible(KeyType, ValueType); |
| 78 |
|
| 79 |
// Check if the comparison type for the algorithm and the container matches. |
| 80 |
if (AlgCall->getNumArgs() == 4 && !Unordered) { |
| 81 |
const Expr *Arg = AlgCall->getArg(3); |
| 82 |
const QualType AlgCmp = |
| 83 |
Arg->getType().getUnqualifiedType().getCanonicalType(); |
| 84 |
const unsigned CmpPosition = IneffContName.contains("map") ? 2 : 1; |
| 85 |
const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition] |
| 86 |
.getAsType() |
| 87 |
.getUnqualifiedType() |
| 88 |
.getCanonicalType(); |
| 89 |
if (AlgCmp != ContainerCmp) { |
| 90 |
diag(Arg->getBeginLoc(), |
| 91 |
"different comparers used in the algorithm and the container"); |
| 92 |
return; |
| 93 |
} |
| 94 |
} |
| 95 |
|
| 96 |
const auto *AlgDecl = AlgCall->getDirectCallee(); |
| 97 |
if (!AlgDecl) |
| 98 |
return; |
| 99 |
|
| 100 |
if (Unordered && AlgDecl->getName().contains("bound")) |
| 101 |
return; |
| 102 |
|
| 103 |
const auto *AlgParam = Result.Nodes.getNodeAs<Expr>("AlgParam"); |
| 104 |
const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr"); |
| 105 |
FixItHint Hint; |
| 106 |
|
| 107 |
SourceManager &SM = *Result.SourceManager; |
| 108 |
LangOptions LangOpts = getLangOpts(); |
| 109 |
|
| 110 |
CharSourceRange CallRange = |
| 111 |
CharSourceRange::getTokenRange(AlgCall->getSourceRange()); |
| 112 |
|
| 113 |
// FIXME: Create a common utility to extract a file range that the given token |
| 114 |
// sequence is exactly spelled at (without macro argument expansions etc.). |
| 115 |
// We can't use Lexer::makeFileCharRange here, because for |
| 116 |
// |
| 117 |
// #define F(x) x |
| 118 |
// x(a b c); |
| 119 |
// |
| 120 |
// it will return "x(a b c)", when given the range "a"-"c". It makes sense for |
| 121 |
// removals, but not for replacements. |
| 122 |
// |
| 123 |
// This code is over-simplified, but works for many real cases. |
| 124 |
if (SM.isMacroArgExpansion(CallRange.getBegin()) && |
| 125 |
SM.isMacroArgExpansion(CallRange.getEnd())) { |
| 126 |
CallRange.setBegin(SM.getSpellingLoc(CallRange.getBegin())); |
| 127 |
CallRange.setEnd(SM.getSpellingLoc(CallRange.getEnd())); |
| 128 |
} |
| 129 |
|
| 130 |
if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) { |
| 131 |
StringRef ContainerText = Lexer::getSourceText( |
| 132 |
CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM, |
| 133 |
LangOpts); |
| 134 |
StringRef ParamText = Lexer::getSourceText( |
| 135 |
CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM, |
| 136 |
LangOpts); |
| 137 |
std::string ReplacementText = |
| 138 |
(llvm::Twine(ContainerText) + (PtrToContainer ? "->" : ".") + |
| 139 |
AlgDecl->getName() + "(" + ParamText + ")") |
| 140 |
.str(); |
| 141 |
Hint = FixItHint::CreateReplacement(CallRange, ReplacementText); |
| 142 |
} |
| 143 |
|
| 144 |
diag(AlgCall->getBeginLoc(), |
| 145 |
"this STL algorithm call should be replaced with a container method") |
| 146 |
<< Hint; |
| 147 |
} |
| 148 |
|
| 149 |
} // namespace clang::tidy::performance |