10 #include "clang/AST/ASTContext.h"
11 #include "clang/ASTMatchers/ASTMatchFinder.h"
12 #include "clang/Lex/Lexer.h"
18 namespace performance {
21 if (
const auto *LeftRefType = Left->getAs<ReferenceType>())
22 Left = LeftRefType->getPointeeType();
23 if (
const auto *RightRefType = Right->getAs<ReferenceType>())
24 Right = RightRefType->getPointeeType();
25 return Left->getCanonicalTypeUnqualified() ==
26 Right->getCanonicalTypeUnqualified();
29 void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) {
30 const auto Algorithms =
31 hasAnyName(
"::std::find",
"::std::count",
"::std::equal_range",
32 "::std::lower_bound",
"::std::upper_bound");
33 const auto ContainerMatcher = classTemplateSpecializationDecl(hasAnyName(
34 "::std::set",
"::std::map",
"::std::multiset",
"::std::multimap",
35 "::std::unordered_set",
"::std::unordered_map",
36 "::std::unordered_multiset",
"::std::unordered_multimap"));
40 callee(functionDecl(Algorithms)),
43 callee(cxxMethodDecl(hasName(
"begin"))),
45 hasDeclaration(decl().bind(
"IneffContObj")),
46 anyOf(hasType(ContainerMatcher.bind(
"IneffCont")),
48 ContainerMatcher.bind(
"IneffContPtr")))))
49 .bind(
"IneffContExpr")))),
51 1, cxxMemberCallExpr(callee(cxxMethodDecl(hasName(
"end"))),
52 on(declRefExpr(hasDeclaration(
53 equalsBoundNode(
"IneffContObj")))))),
54 hasArgument(2, expr().bind(
"AlgParam")))
57 Finder->addMatcher(Matcher,
this);
61 const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>(
"IneffAlg");
62 const auto *IneffCont =
63 Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>(
"IneffCont");
64 bool PtrToContainer =
false;
67 Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>(
"IneffContPtr");
68 PtrToContainer =
true;
70 const llvm::StringRef IneffContName = IneffCont->getName();
71 const bool Unordered =
72 IneffContName.find(
"unordered") != llvm::StringRef::npos;
73 const bool Maplike = IneffContName.find(
"map") != llvm::StringRef::npos;
77 QualType ValueType = AlgCall->getArg(2)->getType();
79 IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType();
83 if (AlgCall->getNumArgs() == 4 && !Unordered) {
84 const Expr *Arg = AlgCall->getArg(3);
85 const QualType AlgCmp =
86 Arg->getType().getUnqualifiedType().getCanonicalType();
87 const unsigned CmpPosition =
88 (IneffContName.find(
"map") == llvm::StringRef::npos) ? 1 : 2;
89 const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition]
93 if (AlgCmp != ContainerCmp) {
94 diag(Arg->getBeginLoc(),
95 "different comparers used in the algorithm and the container");
100 const auto *AlgDecl = AlgCall->getDirectCallee();
104 if (Unordered && AlgDecl->getName().find(
"bound") != llvm::StringRef::npos)
107 const auto *AlgParam = Result.Nodes.getNodeAs<Expr>(
"AlgParam");
108 const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>(
"IneffContExpr");
111 SourceManager &SM = *Result.SourceManager;
112 LangOptions
LangOpts = getLangOpts();
114 CharSourceRange CallRange =
115 CharSourceRange::getTokenRange(AlgCall->getSourceRange());
128 if (SM.isMacroArgExpansion(CallRange.getBegin()) &&
129 SM.isMacroArgExpansion(CallRange.getEnd())) {
130 CallRange.setBegin(SM.getSpellingLoc(CallRange.getBegin()));
131 CallRange.setEnd(SM.getSpellingLoc(CallRange.getEnd()));
134 if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) {
136 CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM,
139 CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM,
141 std::string ReplacementText =
142 (llvm::Twine(ContainerText) + (PtrToContainer ?
"->" :
".") +
143 AlgDecl->getName() +
"(" + ParamText +
")")
145 Hint = FixItHint::CreateReplacement(CallRange, ReplacementText);
148 diag(AlgCall->getBeginLoc(),
149 "this STL algorithm call should be replaced with a container method")