323 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 "UseRangesCheck.h"10#include "Matchers.h"11#include "clang/AST/ASTContext.h"12#include "clang/AST/Decl.h"13#include "clang/AST/Expr.h"14#include "clang/ASTMatchers/ASTMatchFinder.h"15#include "clang/ASTMatchers/ASTMatchers.h"16#include "clang/ASTMatchers/ASTMatchersInternal.h"17#include "clang/Basic/Diagnostic.h"18#include "clang/Basic/LLVM.h"19#include "clang/Basic/SourceLocation.h"20#include "clang/Basic/SourceManager.h"21#include "clang/Lex/Lexer.h"22#include "llvm/ADT/ArrayRef.h"23#include "llvm/ADT/STLExtras.h"24#include "llvm/ADT/SmallBitVector.h"25#include "llvm/ADT/SmallVector.h"26#include "llvm/ADT/StringRef.h"27#include "llvm/ADT/Twine.h"28#include "llvm/Support/raw_ostream.h"29#include <cassert>30#include <optional>31#include <string>32 33using namespace clang::ast_matchers;34 35static constexpr const char BoundCall[] = "CallExpr";36static constexpr const char FuncDecl[] = "FuncDecl";37static constexpr const char ArgName[] = "ArgName";38 39namespace clang::tidy::utils {40 41static std::string getFullPrefix(ArrayRef<UseRangesCheck::Indexes> Signature) {42 std::string Output;43 llvm::raw_string_ostream OS(Output);44 for (const UseRangesCheck::Indexes &Item : Signature)45 OS << Item.BeginArg << ":" << Item.EndArg << ":"46 << (Item.ReplaceArg == UseRangesCheck::Indexes::First ? '0' : '1');47 return Output;48}49 50namespace {51 52AST_MATCHER(Expr, hasSideEffects) {53 return Node.HasSideEffects(Finder->getASTContext());54}55} // namespace56 57static auto58makeExprMatcher(const ast_matchers::internal::Matcher<Expr> &ArgumentMatcher,59 ArrayRef<StringRef> MethodNames,60 ArrayRef<StringRef> FreeNames) {61 return expr(62 anyOf(cxxMemberCallExpr(argumentCountIs(0),63 callee(cxxMethodDecl(hasAnyName(MethodNames))),64 on(ArgumentMatcher)),65 callExpr(argumentCountIs(1), hasArgument(0, ArgumentMatcher),66 hasDeclaration(functionDecl(hasAnyName(FreeNames))))));67}68 69static ast_matchers::internal::Matcher<CallExpr>70makeMatcherPair(StringRef State, const UseRangesCheck::Indexes &Indexes,71 ArrayRef<StringRef> BeginFreeNames,72 ArrayRef<StringRef> EndFreeNames,73 const std::optional<UseRangesCheck::ReverseIteratorDescriptor>74 &ReverseDescriptor) {75 std::string ArgBound = (ArgName + llvm::Twine(Indexes.BeginArg)).str();76 const SmallString<64> ID = {BoundCall, State};77 ast_matchers::internal::Matcher<CallExpr> ArgumentMatcher = allOf(78 hasArgument(Indexes.BeginArg,79 makeExprMatcher(expr(unless(hasSideEffects())).bind(ArgBound),80 {"begin", "cbegin"}, BeginFreeNames)),81 hasArgument(Indexes.EndArg,82 makeExprMatcher(83 expr(matchers::isStatementIdenticalToBoundNode(ArgBound)),84 {"end", "cend"}, EndFreeNames)));85 if (ReverseDescriptor) {86 ArgBound.push_back('R');87 const SmallVector<StringRef> RBegin{88 llvm::make_first_range(ReverseDescriptor->FreeReverseNames)};89 const SmallVector<StringRef> REnd{90 llvm::make_second_range(ReverseDescriptor->FreeReverseNames)};91 ArgumentMatcher = anyOf(92 ArgumentMatcher,93 allOf(hasArgument(94 Indexes.BeginArg,95 makeExprMatcher(expr(unless(hasSideEffects())).bind(ArgBound),96 {"rbegin", "crbegin"}, RBegin)),97 hasArgument(98 Indexes.EndArg,99 makeExprMatcher(100 expr(matchers::isStatementIdenticalToBoundNode(ArgBound)),101 {"rend", "crend"}, REnd))));102 }103 return callExpr(argumentCountAtLeast(104 std::max(Indexes.BeginArg, Indexes.EndArg) + 1),105 ArgumentMatcher)106 .bind(ID);107}108 109void UseRangesCheck::registerMatchers(MatchFinder *Finder) {110 auto Replaces = getReplacerMap();111 ReverseDescriptor = getReverseDescriptor();112 auto BeginEndNames = getFreeBeginEndMethods();113 const llvm::SmallVector<StringRef, 4> BeginNames{114 llvm::make_first_range(BeginEndNames)};115 const llvm::SmallVector<StringRef, 4> EndNames{116 llvm::make_second_range(BeginEndNames)};117 Replacers.clear();118 llvm::DenseSet<Replacer *> SeenRepl;119 for (auto I = Replaces.begin(), E = Replaces.end(); I != E; ++I) {120 auto Replacer = I->getValue();121 if (!SeenRepl.insert(Replacer.get()).second)122 continue;123 Replacers.push_back(Replacer);124 assert(!Replacer->getReplacementSignatures().empty() &&125 llvm::all_of(Replacer->getReplacementSignatures(),126 [](auto Index) { return !Index.empty(); }));127 std::vector<StringRef> Names(1, I->getKey());128 for (auto J = std::next(I); J != E; ++J)129 if (J->getValue() == Replacer)130 Names.push_back(J->getKey());131 132 std::vector<ast_matchers::internal::DynTypedMatcher> TotalMatchers;133 // As we match on the first matched signature, we need to sort the134 // signatures in order of length(longest to shortest). This way any135 // signature that is a subset of another signature will be matched after the136 // other.137 SmallVector<Signature> SigVec(Replacer->getReplacementSignatures());138 llvm::sort(SigVec, [](auto &L, auto &R) { return R.size() < L.size(); });139 for (const auto &Signature : SigVec) {140 std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;141 for (const auto &ArgPair : Signature)142 Matchers.push_back(makeMatcherPair(getFullPrefix(Signature), ArgPair,143 BeginNames, EndNames,144 ReverseDescriptor));145 TotalMatchers.push_back(146 ast_matchers::internal::DynTypedMatcher::constructVariadic(147 ast_matchers::internal::DynTypedMatcher::VO_AllOf,148 ASTNodeKind::getFromNodeKind<CallExpr>(), std::move(Matchers)));149 }150 Finder->addMatcher(151 callExpr(152 callee(functionDecl(hasAnyName(Names))153 .bind((FuncDecl + Twine(Replacers.size() - 1).str()))),154 ast_matchers::internal::DynTypedMatcher::constructVariadic(155 ast_matchers::internal::DynTypedMatcher::VO_AnyOf,156 ASTNodeKind::getFromNodeKind<CallExpr>(),157 std::move(TotalMatchers))158 .convertTo<CallExpr>()),159 this);160 }161}162 163static void removeFunctionArgs(DiagnosticBuilder &Diag, const CallExpr &Call,164 ArrayRef<unsigned> Indexes,165 const ASTContext &Ctx) {166 llvm::SmallVector<unsigned> Sorted(Indexes);167 llvm::sort(Sorted);168 // Keep track of commas removed169 llvm::SmallBitVector Commas(Call.getNumArgs());170 // The first comma is actually the '(' which we can't remove171 Commas[0] = true;172 for (const unsigned Index : Sorted) {173 const Expr *Arg = Call.getArg(Index);174 if (Commas[Index]) {175 if (Index >= Commas.size()) {176 Diag << FixItHint::CreateRemoval(Arg->getSourceRange());177 } else {178 // Remove the next comma179 Commas[Index + 1] = true;180 Diag << FixItHint::CreateRemoval(CharSourceRange::getTokenRange(181 {Arg->getBeginLoc(),182 Lexer::getLocForEndOfToken(183 Arg->getEndLoc(), 0, Ctx.getSourceManager(), Ctx.getLangOpts())184 .getLocWithOffset(1)}));185 }186 } else {187 Diag << FixItHint::CreateRemoval(CharSourceRange::getTokenRange(188 Arg->getBeginLoc().getLocWithOffset(-1), Arg->getEndLoc()));189 Commas[Index] = true;190 }191 }192}193 194void UseRangesCheck::check(const MatchFinder::MatchResult &Result) {195 const Replacer *Replacer = nullptr;196 const FunctionDecl *Function = nullptr;197 for (const auto &[Node, Value] : Result.Nodes.getMap()) {198 StringRef NodeStr(Node);199 if (!NodeStr.consume_front(FuncDecl))200 continue;201 Function = Value.get<FunctionDecl>();202 size_t Index;203 if (NodeStr.getAsInteger(10, Index)) {204 llvm_unreachable("Unable to extract replacer index");205 }206 assert(Index < Replacers.size());207 Replacer = Replacers[Index].get();208 break;209 }210 assert(Replacer && Function);211 SmallString<64> Buffer;212 for (const Signature &Sig : Replacer->getReplacementSignatures()) {213 Buffer.assign({BoundCall, getFullPrefix(Sig)});214 const auto *Call = Result.Nodes.getNodeAs<CallExpr>(Buffer);215 if (!Call)216 continue;217 218 // FIXME: This check specifically handles `CXXNullPtrLiteralExpr`, but219 // a more general solution might be needed.220 if (Function->getName() == "find") {221 const unsigned ValueArgIndex = 2;222 if (Call->getNumArgs() <= ValueArgIndex)223 continue;224 const Expr *ValueExpr =225 Call->getArg(ValueArgIndex)->IgnoreParenImpCasts();226 if (isa<CXXNullPtrLiteralExpr>(ValueExpr))227 return;228 }229 230 auto Diag = createDiag(*Call);231 if (auto ReplaceName = Replacer->getReplaceName(*Function))232 Diag << FixItHint::CreateReplacement(Call->getCallee()->getSourceRange(),233 *ReplaceName);234 if (auto Include = Replacer->getHeaderInclusion(*Function))235 Diag << Inserter.createIncludeInsertion(236 Result.SourceManager->getFileID(Call->getBeginLoc()), *Include);237 llvm::SmallVector<unsigned, 3> ToRemove;238 for (const auto &[First, Second, Replace] : Sig) {239 auto ArgNode = ArgName + std::to_string(First);240 if (const auto *ArgExpr = Result.Nodes.getNodeAs<Expr>(ArgNode)) {241 Diag << FixItHint::CreateReplacement(242 Call->getArg(Replace == Indexes::Second ? Second : First)243 ->getSourceRange(),244 Lexer::getSourceText(245 CharSourceRange::getTokenRange(ArgExpr->getSourceRange()),246 Result.Context->getSourceManager(),247 Result.Context->getLangOpts()));248 } else {249 assert(ReverseDescriptor && "Couldn't find forward argument");250 ArgNode.push_back('R');251 ArgExpr = Result.Nodes.getNodeAs<Expr>(ArgNode);252 assert(ArgExpr && "Couldn't find forward or reverse argument");253 if (ReverseDescriptor->ReverseHeader)254 Diag << Inserter.createIncludeInsertion(255 Result.SourceManager->getFileID(Call->getBeginLoc()),256 *ReverseDescriptor->ReverseHeader);257 const StringRef ArgText = Lexer::getSourceText(258 CharSourceRange::getTokenRange(ArgExpr->getSourceRange()),259 Result.Context->getSourceManager(), Result.Context->getLangOpts());260 SmallString<128> ReplaceText;261 if (ReverseDescriptor->IsPipeSyntax)262 ReplaceText.assign(263 {ArgText, " | ", ReverseDescriptor->ReverseAdaptorName});264 else265 ReplaceText.assign(266 {ReverseDescriptor->ReverseAdaptorName, "(", ArgText, ")"});267 Diag << FixItHint::CreateReplacement(268 Call->getArg(Replace == Indexes::Second ? Second : First)269 ->getSourceRange(),270 ReplaceText);271 }272 ToRemove.push_back(Replace == Indexes::Second ? First : Second);273 }274 removeFunctionArgs(Diag, *Call, ToRemove, *Result.Context);275 return;276 }277 llvm_unreachable("No valid signature found");278}279 280bool UseRangesCheck::isLanguageVersionSupported(281 const LangOptions &LangOpts) const {282 return LangOpts.CPlusPlus11;283}284 285UseRangesCheck::UseRangesCheck(StringRef Name, ClangTidyContext *Context)286 : ClangTidyCheck(Name, Context),287 Inserter(Options.getLocalOrGlobal("IncludeStyle",288 utils::IncludeSorter::IS_LLVM),289 areDiagsSelfContained()) {}290 291void UseRangesCheck::registerPPCallbacks(const SourceManager &,292 Preprocessor *PP, Preprocessor *) {293 Inserter.registerPreprocessor(PP);294}295 296void UseRangesCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {297 Options.store(Opts, "IncludeStyle", Inserter.getStyle());298}299 300std::optional<std::string>301UseRangesCheck::Replacer::getHeaderInclusion(const NamedDecl &) const {302 return std::nullopt;303}304 305DiagnosticBuilder UseRangesCheck::createDiag(const CallExpr &Call) {306 return diag(Call.getBeginLoc(), "use a ranges version of this algorithm");307}308 309std::optional<UseRangesCheck::ReverseIteratorDescriptor>310UseRangesCheck::getReverseDescriptor() const {311 return std::nullopt;312}313 314ArrayRef<std::pair<StringRef, StringRef>>315UseRangesCheck::getFreeBeginEndMethods() const {316 return {};317}318 319std::optional<TraversalKind> UseRangesCheck::getCheckTraversalKind() const {320 return TK_IgnoreUnlessSpelledInSource;321}322} // namespace clang::tidy::utils323