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
14using namespace clang::ast_matchers;
15
16namespace clang::tidy::performance {
17
18static 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
27void 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(InnerMatcher: functionDecl(Algorithms)),
39 hasArgument(
40 N: 0, InnerMatcher: cxxMemberCallExpr(
41 callee(InnerMatcher: cxxMethodDecl(hasName(Name: "begin"))),
42 on(InnerMatcher: declRefExpr(
43 hasDeclaration(InnerMatcher: decl().bind(ID: "IneffContObj")),
44 anyOf(hasType(InnerMatcher: ContainerMatcher.bind(ID: "IneffCont")),
45 hasType(InnerMatcher: pointsTo(
46 InnerMatcher: ContainerMatcher.bind(ID: "IneffContPtr")))))
47 .bind(ID: "IneffContExpr")))),
48 hasArgument(
49 N: 1, InnerMatcher: cxxMemberCallExpr(callee(InnerMatcher: cxxMethodDecl(hasName(Name: "end"))),
50 on(InnerMatcher: declRefExpr(hasDeclaration(
51 InnerMatcher: equalsBoundNode(ID: "IneffContObj")))))),
52 hasArgument(N: 2, InnerMatcher: expr().bind(ID: "AlgParam")))
53 .bind(ID: "IneffAlg");
54
55 Finder->addMatcher(NodeMatch: Matcher, Action: this);
56}
57
58void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) {
59 const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>(ID: "IneffAlg");
60 const auto *IneffCont =
61 Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>(ID: "IneffCont");
62 bool PtrToContainer = false;
63 if (!IneffCont) {
64 IneffCont =
65 Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>(ID: "IneffContPtr");
66 PtrToContainer = true;
67 }
68 const llvm::StringRef IneffContName = IneffCont->getName();
69 const bool Unordered = IneffContName.contains(Other: "unordered");
70 const bool Maplike = IneffContName.contains(Other: "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(Arg: 2)->getType();
75 QualType KeyType =
76 IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType();
77 const bool CompatibleTypes = areTypesCompatible(Left: KeyType, Right: 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(Arg: 3);
82 const QualType AlgCmp =
83 Arg->getType().getUnqualifiedType().getCanonicalType();
84 const unsigned CmpPosition = IneffContName.contains(Other: "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>(ID: "AlgParam");
104 const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>(ID: "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(Loc: CallRange.getBegin()) &&
125 SM.isMacroArgExpansion(Loc: CallRange.getEnd())) {
126 CallRange.setBegin(SM.getSpellingLoc(Loc: CallRange.getBegin()));
127 CallRange.setEnd(SM.getSpellingLoc(Loc: CallRange.getEnd()));
128 }
129
130 if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) {
131 StringRef ContainerText = Lexer::getSourceText(
132 Range: CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM,
133 LangOpts);
134 StringRef ParamText = Lexer::getSourceText(
135 Range: 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(RemoveRange: CallRange, Code: ReplacementText);
142 }
143
144 diag(Loc: AlgCall->getBeginLoc(),
145 Description: "this STL algorithm call should be replaced with a container method")
146 << Hint;
147}
148
149} // namespace clang::tidy::performance
150

source code of clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp