150 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//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(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 58void 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 value73 // that is searched for.74 const QualType ValueType = AlgCall->getArg(2)->getType();75 const 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 const SourceManager &SM = *Result.SourceManager;108 const 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 token114 // sequence is exactly spelled at (without macro argument expansions etc.).115 // We can't use Lexer::makeFileCharRange here, because for116 //117 // #define F(x) x118 // x(a b c);119 //120 // it will return "x(a b c)", when given the range "a"-"c". It makes sense for121 // 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 const StringRef ContainerText = Lexer::getSourceText(132 CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM,133 LangOpts);134 const StringRef ParamText = Lexer::getSourceText(135 CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM,136 LangOpts);137 const 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::performance150