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 {
17 namespace tidy {
18 namespace performance {
19
areTypesCompatible(QualType Left,QualType Right)20 static bool areTypesCompatible(QualType Left, QualType Right) {
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();
27 }
28
registerMatchers(MatchFinder * Finder)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"));
37
38 const auto Matcher =
39 callExpr(
40 callee(functionDecl(Algorithms)),
41 hasArgument(
42 0, cxxMemberCallExpr(
43 callee(cxxMethodDecl(hasName("begin"))),
44 on(declRefExpr(
45 hasDeclaration(decl().bind("IneffContObj")),
46 anyOf(hasType(ContainerMatcher.bind("IneffCont")),
47 hasType(pointsTo(
48 ContainerMatcher.bind("IneffContPtr")))))
49 .bind("IneffContExpr")))),
50 hasArgument(
51 1, cxxMemberCallExpr(callee(cxxMethodDecl(hasName("end"))),
52 on(declRefExpr(hasDeclaration(
53 equalsBoundNode("IneffContObj")))))),
54 hasArgument(2, expr().bind("AlgParam")))
55 .bind("IneffAlg");
56
57 Finder->addMatcher(Matcher, this);
58 }
59
check(const MatchFinder::MatchResult & Result)60 void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) {
61 const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>("IneffAlg");
62 const auto *IneffCont =
63 Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffCont");
64 bool PtrToContainer = false;
65 if (!IneffCont) {
66 IneffCont =
67 Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffContPtr");
68 PtrToContainer = true;
69 }
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;
74
75 // Store if the key type of the container is compatible with the value
76 // that is searched for.
77 QualType ValueType = AlgCall->getArg(2)->getType();
78 QualType KeyType =
79 IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType();
80 const bool CompatibleTypes = areTypesCompatible(KeyType, ValueType);
81
82 // Check if the comparison type for the algorithm and the container matches.
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]
90 .getAsType()
91 .getUnqualifiedType()
92 .getCanonicalType();
93 if (AlgCmp != ContainerCmp) {
94 diag(Arg->getBeginLoc(),
95 "different comparers used in the algorithm and the container");
96 return;
97 }
98 }
99
100 const auto *AlgDecl = AlgCall->getDirectCallee();
101 if (!AlgDecl)
102 return;
103
104 if (Unordered && AlgDecl->getName().find("bound") != llvm::StringRef::npos)
105 return;
106
107 const auto *AlgParam = Result.Nodes.getNodeAs<Expr>("AlgParam");
108 const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr");
109 FixItHint Hint;
110
111 SourceManager &SM = *Result.SourceManager;
112 LangOptions LangOpts = getLangOpts();
113
114 CharSourceRange CallRange =
115 CharSourceRange::getTokenRange(AlgCall->getSourceRange());
116
117 // FIXME: Create a common utility to extract a file range that the given token
118 // sequence is exactly spelled at (without macro argument expansions etc.).
119 // We can't use Lexer::makeFileCharRange here, because for
120 //
121 // #define F(x) x
122 // x(a b c);
123 //
124 // it will return "x(a b c)", when given the range "a"-"c". It makes sense for
125 // removals, but not for replacements.
126 //
127 // This code is over-simplified, but works for many real cases.
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()));
132 }
133
134 if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) {
135 StringRef ContainerText = Lexer::getSourceText(
136 CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM,
137 LangOpts);
138 StringRef ParamText = Lexer::getSourceText(
139 CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM,
140 LangOpts);
141 std::string ReplacementText =
142 (llvm::Twine(ContainerText) + (PtrToContainer ? "->" : ".") +
143 AlgDecl->getName() + "(" + ParamText + ")")
144 .str();
145 Hint = FixItHint::CreateReplacement(CallRange, ReplacementText);
146 }
147
148 diag(AlgCall->getBeginLoc(),
149 "this STL algorithm call should be replaced with a container method")
150 << Hint;
151 }
152
153 } // namespace performance
154 } // namespace tidy
155 } // namespace clang
156