1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
//===--- InefficientAlgorithmCheck.cpp - clang-tidy------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include "InefficientAlgorithmCheck.h"
#include "clang/AST/ASTContext.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/Lex/Lexer.h"
using namespace clang::ast_matchers;
namespace clang {
namespace tidy {
void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) {
const std::string Algorithms =
"^::std::(find|count|equal_range|lower_blound|upper_bound)$";
const auto ContainerMatcher = classTemplateSpecializationDecl(
matchesName("^::std::(unordered_)?(multi)?(set|map)$"));
const auto Matcher =
callExpr(
callee(functionDecl(matchesName(Algorithms))),
hasArgument(
0, constructExpr(has(memberCallExpr(
callee(methodDecl(hasName("begin"))),
on(declRefExpr(
hasDeclaration(decl().bind("IneffContObj")),
anyOf(hasType(ContainerMatcher.bind("IneffCont")),
hasType(pointsTo(
ContainerMatcher.bind("IneffContPtr")))))
.bind("IneffContExpr")))))),
hasArgument(1, constructExpr(has(memberCallExpr(
callee(methodDecl(hasName("end"))),
on(declRefExpr(hasDeclaration(
equalsBoundNode("IneffContObj")))))))),
hasArgument(2, expr().bind("AlgParam")),
unless(isInTemplateInstantiation())).bind("IneffAlg");
Finder->addMatcher(Matcher, this);
}
void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) {
const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>("IneffAlg");
const auto *IneffCont =
Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffCont");
bool PtrToContainer = false;
if (!IneffCont) {
IneffCont =
Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffContPtr");
PtrToContainer = true;
}
const llvm::StringRef IneffContName = IneffCont->getName();
const bool Unordered =
IneffContName.find("unordered") != llvm::StringRef::npos;
// Check if the comparison type for the algorithm and the container matches.
if (AlgCall->getNumArgs() == 4 && !Unordered) {
const Expr *Arg = AlgCall->getArg(3);
const QualType AlgCmp =
Arg->getType().getUnqualifiedType().getCanonicalType();
const unsigned CmpPosition =
(IneffContName.find("map") == llvm::StringRef::npos) ? 1 : 2;
const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition]
.getAsType()
.getUnqualifiedType()
.getCanonicalType();
if (AlgCmp != ContainerCmp) {
diag(Arg->getLocStart(),
"different comparers used in the algorithm and the container");
return;
}
}
const auto *AlgDecl = AlgCall->getDirectCallee();
if (!AlgDecl)
return;
if (Unordered && AlgDecl->getName().find("bound") != llvm::StringRef::npos)
return;
const auto *AlgParam = Result.Nodes.getNodeAs<Expr>("AlgParam");
const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr");
FixItHint Hint;
if (!AlgCall->getLocStart().isMacroID()) {
std::string ReplacementText =
(llvm::Twine(Lexer::getSourceText(
CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()),
*Result.SourceManager, Result.Context->getLangOpts())) +
(PtrToContainer ? "->" : ".") + AlgDecl->getName() + "(" +
Lexer::getSourceText(
CharSourceRange::getTokenRange(AlgParam->getSourceRange()),
*Result.SourceManager, Result.Context->getLangOpts()) +
")").str();
Hint = FixItHint::CreateReplacement(AlgCall->getSourceRange(),
ReplacementText);
}
diag(AlgCall->getLocStart(),
"this STL algorithm call should be replaced with a container method")
<< Hint;
}
} // namespace tidy
} // namespace clang
|
